Skip to content

背包問題 - 簡單版

問題概述

故事

今天你想出門旅行，需要有一個大背包裝行李，雖然想帶的東西很多，但是背包空間、你的負重都必須有所限制…，求能裝最多東西的塞法?

NP 問題

背包問題可以非常複雜(NP問題)
比如為負重、長、寬、高、效用做限制 今天有
洋芋片 (10,20,20,40,50)
換洗衣物 (5,5,5,5,200)
錢包 (50,10,10,5,1000)
神秘小方塊 (40,1,1,1,10000)

背包的限制是 (60,25,25,25)，求效用極大化的放法
光是這樣就是5個維度要去檢查，可以想像其複雜程度

簡化

這篇要討論的是簡化版
意即給定一個限制數字s，與一個數字陣列arr
求不超過s的情況下，從arr中湊出最大的數字和

可以把s想像成負重
arr是欲放入物品的重量

舉例而言
s=6
arr = [2,3,5,8]

則最大和就是 2+3 == 5 ，無法再加入其他數字
從例子中也可以看出解並不唯一，比如也可以單放5作為答案

暴力解

概念

以上述例子而言
可以想像答案一定在 每個東西都放入 ~ 每個東西不放入 之間
也就是
2^4 種可能中，尋找最大值

概念上為

可以觀察到:

  • 有些明顯就放不進去，就不需要討論，進行剪枝即可
  • 最後的確有抓到兩個解
  • 最多會有2^(len(arr))的運算結果

因此複雜度為O(2^N)，N是arr的長度，也就是選擇數量

這比起多項式時間是成長非常快的複雜度
因此通常不能直接這樣解

程式碼

def backpack (current_limit , arr , current_index):
	if len(arr) == current_index:
		return current_limit

	if current_limit < 0 :
		return current_limit+1  # error

	return min(backpack(current_limit-arr[current_index],arr, current_index+1), backpack(current_limit,arr, current_index+1))  #放入與不放入，同時記得index+1

得到current_limit最小值後， 用current_limit 減去就能得到最大值

如果能把限制剛好填滿(即 backpack(current_limit,arr,0) == 0)，我們視為有解

DP 改良

遞迴演算法，很常可以用DP來提速
通常就是建造table去紀錄前幾項，避免重複計算的部分

概念上， 要問重量限制是10的背包，重量為4(第i個)東西可不可以放進去
可以改問重量限制是10-4 == 6 的背包，可不可以放第i+1個東西進去

因此我們需要從limit小 => 大 去紀錄答案
同時因為有N個選擇，可以建一個二維表格去紀錄

說明:

  1. 符號O表示 沒放進去，並且有解
    符號I表示 放進去，並且有解
    符號-表示 沒有解

  2. 起始值，因為limit==0中，都不放入就有解
    所以limit == 0 那行可以全部填O

  3. 要分為"放進去” or “沒放進” 討論:

    • 放進去
      查看限制是 limit - 當前值 ， 編號是 上一號是否有解，
      如果有解，當前值放進去也一定有解
    • 沒放進去
      查看 編號上一號 是否有解
      有解的話不放進去也一定有解

  4. 從上而下，從左而右完成表格

演算法

# make table
Table = [['-' for i in range(limit) ] for i in range(len(arr))]

# Table[i][j] 表示 第i個選擇，limit = j

# initialize
for i in range(len(arr)):
	Table[i][0] = 'O'

# DP 
for j in range(limit):
	current_limit = j
	for i in range(1,len(arr)):
		if current_limit > arr[i] and Table[i-1][current_limit - arr[i]] = 'I' or 'O':  
			Table[i][j] = 'I'   # 在確定符合index範圍後檢查是否放入
			continue
		elif j>0 and Table[i-1][j] == 'I' or 'O':	
			Table[i][j] = 'O' 
			continue 
		else:
			Table[i][j] = '-'

BackTrack

在製表完成後，如果有解，可以依最右下角
依反規則推得解的path

如果本格是 O ， 表示往上一格是解
如果本格是 I , 表示limit-本格的上一格 是解
如下圖

時間複雜度

可以由O(2^N) 降至 O(N*limit*N) 的時間

存放文章數: 53

連結

分類