0-1背包問題的動態規劃演算法

01-31

題圖是想致敬亂馬1/2八寶齋。

首先得知道什麼是0-1背包問題（knapsack problem）

?? 賊，夜入豪宅，可偷之物甚多，而負重能力有限，偷哪些才更加不枉此行？

?? 抽象的話，就是：

給定一組多個（ $n$ ）物品，每種物品都有自己的重量（ $w_i$ ）和價值（ $v_i$ ），在限定的總重量/總容量（ $C$ ）內，選擇其中若干個（也即每種物品可以選0個或1個），設計選擇方案使得物品的總價值最高。

?? 更加抽象的話：

給定正整數 ${(w_i,v_i)}_{1leq ileq n}$ 、給定正整數 $C$ ，求解0-1規劃問題：

$max sum_{i=1}^{n}{x_iv_i}$ ， s.t. $sum_{i=1}^{n}{x_iw_i}leq C$ ， $x_iin{0,1}$ 。

?? 示例應用：處理器能力有限時間受限，任務很多，如何選擇使得總效用最大？

?? 數值例子：如下圖。

0-1背包問題的定性

?? 對於一般性的0-1背包，

貪婪演算法無法得到最優解。

反例，不多解釋——

事實上它可能想多差有多差（以 $v/w$ 作為「貪婪」的標準，也不多解釋了）——

?? 確定性問題版本的背包問題是NP的，

「 $w_i=v_i$ ，求 $x_iin{0,1}$ 使得 $sum_{i=1}^{n}{x_iw_i}= C$ 」是Karp的21個NPC問題之一（實際上Karp的表述是現在所稱的子集和（subset sum）問題）。

0-1背包問題的遞推關係

定義子問題 $mathbf{text{P(i, W)}}$ 為：在前 $i$ 個物品中挑選總重量不超過 $W$ 的物品，每種物品至多只能挑選1個，使得總價值最大；這時的最優值記作 $m(i,W)$ ，其中 $1leq ileq n$ ， $1leq Wleq C$ 。

考慮第 $i$ 個物品，無外乎兩種可能：選，或者不選。

不選的話，背包的容量不變，改變為問題 $mathbf{{P(i-1, W)}}$ ；
選的話，背包的容量變小，改變為問題 $mathbf{{P(i-1, W-w_i)}}$ 。

最優方案就是比較這兩種方案，哪個會更好些：

$m(i,W)=max{m(i-1,W),m(i-1,W-w_i)+v_i}$ 。

得到

$[m(i,W)=left{ begin{array}{*{55}{l}} 0 & text{if } i=text{0} 0 & text{if } W=text{0} m(i-1,W) & text{if }{w_i>W} max left{ m(i-1,W),{{v}_{i}}+m(i-1,W-{{w}_{i}}) right} & text{otherwise} end{array} right.]$ 。

「填二維表」的動態規劃方法

演算法就很自然了：

之前的例子填表的結果是——

（藍色格子表示本行值發生變化的格子）

然後發生 $m(i,W)=m(i-1,W-w_i)+v_i$ 時才會有「取第 $i$ 件物品」發生。

所以從表格右下角「往回看」如果是「垂直下降」就是發生了 $m(i,W)=m(i-1,W)$ ，而只有「走斜線」才是「取了」物品。

這個演算法的複雜度就很容易算了——每一個格子都要填寫數字，所以時間複雜度和空間複雜度都是 $Omega(nC)$ 。當" $C>2^n$ "時（就不嚴謹地使用漸近分析的語言了），複雜度是 $Omega(n2^n)$ 。

所謂「填一維表」的動態規劃方法

?? 其實呢，上面那個二維表，也可以用一行來存儲啊！對不啦？

?? 所以，根本的區別在於思想，而不是具體存儲方式。

那麼這個演算法的思想又是什麼呢？——其實就是：

每行都有些數值相同的哦，所以
只記錄每行里那些不同的數值就好了啊。

?? 例如上面的表格中，只記錄藍色的部分，

格式是 $(i,W,m(i,W))$ （為了方便閱讀，再貼一次圖）：

$(0,0,0)$ 、

$(1,0,0)$ 、 $(1,1,1)$ 、

$(2,0,0)$ 、 $(2,1,1)$ 、 $(2,2,6)$ 、 $(2,3,7)$ 、

$(3,0,0)$ 、 $(3,1,1)$ 、 $(3,2,6)$ 、 $(3,3,7)$ 、 $(3,5,18)$ 、 $(3,6,19)$ 、 $(3,7,24)$ 、 $(3,8,25)$ 、

……（不寫了，累）

?? 你會說，這也沒省什麼地方啊？！

的確，對於這個例子來說是這樣的——要不然數值太大我畫不下。

你假設每個 $w_i$ 都擴大1000倍，那樣的話，表格也擴大到1000倍，填表時間也增加到1000倍，然而藍色的格子還是那麼多。

?? 好了，繼續，下面有三個問題：

$m(i,W)geq m(i-1,W)$ ， $m(i,W)geq m(i,W-1)$ ；（這比較顯然）
什麼時候會發生「 $m(i,W)> m(i,W-1)$ 」的情況？
什麼時候會發生「 $m(i,W)> m(i-1,W)$ 」的情況？

?? 下面來看問題2，一定是發生了「容量擴大後有個新的東西可以放下了」！

所以固定 $i$ ，讓 $W$ 變化， $m(i,W)$ 一定是「階梯狀」的：

有的 $w$ 使得 $m(i,w)> m(i,w-1)$ ；
有的 $w$ 使得 $m(i,w)= m(i,w-1)$ 。

例如，前面例子中 $m(1,w)$ 如下圖所示：

看下 $m(2,W)=max{m(1,W),m(1,W-w_2)+v_2}$ ， $m(1,W-w_2)+v_2$ 是 $m(1,W)$ 右移 $w_2$ 上移 $v_2$ 。

所以 $m(2,W)$ （ $w_2=2，v_2=6$ ）就是下述兩條「階梯」

在max意義下的「疊加」。

比較 $m(1,W)$ 和 $m(2,W)$ 的「轉折點」：

$m(1,W)$ 的是 $S^1={(1,0,0),(1,1,1)}$ ； $m(2,W)$ 的是 $S^2={(2,0,0),(2,1,1),(2,2,6),(2,3,7)}$ 。

於是：

對於每一個 $i$ ， $m(i ,W)$ 最多只有 $2^i$ 個「轉折點」——因為 $i$ 個物品，最多只有 $2^i$ 個「選」、「不選」的組合；
$m(2,W)$ 中 $m(1,W-w_2)+v_2$ 那部分的所有可能的「轉折點」就是由 $m(1,W)$ 的每個轉折點 $(1,w,v)$ 變為 $(2,w+w_2,v+v_2)$ ；（「可能」這個詞後面再解釋）
推而廣之， $m(i+1,W)$ 中 $m(i,W-w_{i+1})+v_{i+1}$ 那部分的所有可能的「轉折點」就是由 $m(i,W)$ 的每個轉折點 $(i,w,v)$ 變為 $(i+1,w+w_{i+1},v+v_{i+1})$ 。

設置 $S^0={(0,0,0)}$ ，則由 $S^i$ 得到 $S^{i+1}$ 的所有可能的「轉折點」為 ${(i+1,w+w_{i+1},v+v_{i+1})}:(i,w,v)in S^i$ 。

例如 $m(3,W)$ ：

例如 $m(4,W)$ ， $w_4=6,v_4=22$ ：

這時有些問題：

超過 $C=11$ 的部分可以不用考慮；
綠色的圓形里有些「轉折點」被湮沒了——這就是之前說的「可能」的意思。

來看哦， $S^3={(3,0,0),(3,1,1),(3,2,6),(3,3,7),(3,5,18),(3,6,19),(3,7,24),(3,8,25)}$ 。

於是 $S^4$ 的所有可能應該是

${(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}$

$cup$

${(4,0+6,0+22),(4,1+6,1+22),(4,2+6,6+22),(4,3+6,7+22),$

$(4,5+6,18+22),(4,6+6,19+22),(4,7+6,24+22),(4,8+6,25+22)}$

Ok，首先刪除掉第二分量大於 $C=11$ 的（上圖紅框里）（稱作第一類拋棄），得到

${(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}cup$

${(4,6,22),(4,7,23),(4,8,28),(4,9,29),(4,11,40)}$ 。

然後按第二分量遞增排序，得到：

按道理說，對於階梯函數來說，如果第二分量是遞增的，那麼第三分量也應該是遞增的。但是上圖中紅框里不是哦——事實上它們是「被湮沒」的「轉折點」（上圖的黃色圓形）。

所以哦，棄掉他們（稱作第二類拋棄），得到 ${(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,22),(4,7,24),(4,8,28),(4,9,29),(4,11,40)}$ ，就是下圖。

而最終結果就是 $S^n$ 的最後一項的第三個分量。

由 $S^i$ 得到 $S^{i+1}$ 的過程是（例如）：

$S^3={(3,0,0),(3,1,1),(3,2,6),(3,3,7),(3,5,18),(3,6,19),(3,7,24),(3,8,25)}$

已經按照第二分量遞增排序好，

之後先寫成

${(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}$

然後對第一個三元組，

刪除當前位置之後被「湮沒」的

對第二個三元組，一定是插入當前位置之後，並被立即「湮沒」，

不斷這樣進行下去，並注意第一類拋棄即可得到 $S^4$ 。

令 $S^0={(0,0,0)}$ ，則可以得到（由於分行了，就不在乎三元組的第一分量了）：

然後所謂「一維」存儲，其實就是把它「存儲成了」一維，例如使用兩個一維數組和一個start數組做「分割」：

?? 然後就是如何得到方案——

看 $S^5$ 的最後一個是不是與 $S^4$ 的最後一個相同，相同的話就直接看 $S^4$ ；

$S^4$ 的最後一個與 $S^3$ 的最後一個不同，所以一定拿了物品4，然後看 $S^3$ 第二分量不超過5（= $C-w_4$ ）的最後一個，是 $(5,18)$ ；

$(5,18)$ 與 $S^2$ 的最後一個不同，所以一定拿了物品3；

……然後類推。

?? 最後是分析複雜度：

路線是計算 $S^i$ 的元素個數，然後對 $i$ 求和，就得到了所有「藍色格子」的數量。

然後，

首先，由於 $S^{i+1}$ 在不考慮兩類拋棄的情況下（最差情況就是不發生這兩類拋棄），元素個數恰好等於 $S^i$ 元素數的兩倍；也可以這樣來看——對於每一個 $i$ ， $m(i,W)$ 最多只有 $2^i$ 個「轉折點」；
由 $S^i$ 得到 $S^{i+1}$ 時， $S^i$ 中各組的第二分量、第三分量一定彼此不同，那麼每個 $(i,w,m(i,w))$ 中的 $w$ 的取值範圍是 $0leq wleq C$ ，第三分量的取值範圍是 $0simsum_{k=1}^{i}{v_i}$ 。所以這樣的三元組最多有 $min{C+1,sum_{k=1}^{i}{v_k}+1}$ 個。

對 $i=1sim n$ 求和，得到

$「藍色格子」數目leq (1+2^1+2^2+...+2^n)=O(2^n)$ ;
$「藍色格子」數目leq n(C+1)=O(nC)$ ；
$「藍色格子」數目leq sum_{i=1}^{n}{sum_{k=1}^{i}({v_i}+1)}leq sum_{i=1}^{n}{sum_{k=1}^{n}({v_k}+1)}=n+nsum_{k=1}^{n}{v_k}=O(nsum_{k=1}^{n}{v_k})$

而由 $S^i$ 產生 $S^{i+1}$ 的計算過程主要就是產生一個新的對、插入、刪除（拋棄），所以這個過程的計算量是和 $S^i$ 元素數成正比的。

所以得到，無論空間複雜度還是時間複雜度，都是 $O(min{2^n,nC,nsum_{k=1}^{n}{v_k}})$ 的。

即使 $C>2^n$ ，這時的演算法複雜度也控制在 $O(2^n)$ 之內。