動態規劃 (Dynamic Programming) 之 揹包問題合輯 (Knapsack, Subset Sum, Partition and change making problem )

NO IMAGE

揹包問題一直是動態規劃中的經典問題。這個問題又分成01揹包,完全揹包,多重揹包,分組揹包等等。。我在這裡只記錄下01揹包(0-1knapsack)和完全揹包(unbounded knapsack)。揹包問題的簡單描述就是有一個揹包和一堆物品。每個物品有自己的大小和價值。我們希望在一個特定容量的揹包中放入價值儘可能大的物品。01揹包呢就是每個物品最多隻能放一次,也就是要麼放要麼不放,所以被稱為01揹包。而完全揹包呢就是每個物品可以放無限次。我們更喜歡unbounded knapsack這個名字。因為完全這次詞其實沒有表達清楚不限的意思。下面就是對完全揹包和01揹包就動態規劃的方法做一些解析。

 

這兩個問題中似乎01揹包比較爽快,就從爽快的先說。類似的,我們還是要找到一個優化的子結構,然後遞迴式,然後程式碼。。

我們用M[i,j]來表示選用1…i件物品放入容量為j的揹包時最大的價值。那樣就吧這個情況分成2中情況分析。很簡單。用這第i個物品,或者不用。如果不用那麼M[i,j]就等於M[i-1,j](如果看不明白可以想象一下M的定義,這裡M[i-1,j]的意義就是用1…i-1個物品來裝容量為j的揹包時的最優策略,也就是不用第i個物品了。) 。那如果用呢?那就是M[i-1, j – si ] vi。(因為前面的策略已經滿了j個容量,所以如果選用第i個物品,就要把總的容量j中減去第i個物品的容量,然後找到對應的M[i-1, j – si]加i的價值) 然後取一個大的值來決定選用那種策略。這個描述雖然有點拗口,但仔細琢磨意思還是直觀的。所以這個表示式可以寫成

M[i,j] = max { M[i-1,j], M[i-1,j-si] vi }. 如果我們把他放在二維陣列裡面的話,可以看出來這裡的M[i,j]取決與上一層的M[i-1]中的2個元素。

knapsack1

接下來我們再來看看完全揹包的問題。當然在這裡M[i,j]就不是選擇或者不選擇i能夠決定的。而是選擇哪個i是合適。所以我們把i從這個M[i,j]中搬出去,尋找一個更簡潔的表示法。M[j]表示容量為j時的最優方案。這個方案取決與所有M[1…j-1]的值。那怎麼表示呢?可以寫成

M(j) = max { M(j-1), max {M(j-si) vi, si<j } }


knapsack

可以理解成M[j]取決與任何一個si<j的子結構加上pi的最大值。如果一個都不存在那就取決於M[j-1]。或者說從M[1…j-1]中選擇某些個最優的方案。M[j-s1].M[j-s2].. M[j-sn]這些方案加上現有的si可能組成可能的M[j]的方案,找到這些子方案的最優值。這樣就可以保證得到的M[j]是最優的。

下面就是一個實現好的C 程式碼:

 

現在我們手上有了這些解決方案就可以順帶看看其他一些類似的問題。希望可以用現有的方案來解釋那些類似的問題。

1. Subset Sum Problem. Partition Problem. 這是兩個類似的問題。Subset Sum Problem被稱為子集和問題。題目的意思是給定一個集合,判斷是否存在和等於某特定值s的子集。 Partition Problem的中文名字我不知道:)但是題目的意思是一個給定的集合A,把他分成A1和A2兩個子集。使得兩個子集合的差|A1-A2|儘量小。第二個問題其實可以轉化成第一個問題。可以找到全集A的合1/2。然後找到和A/2最接近的子集就可以了。這樣的問題和01揹包還是很類似的。我們依然定義一個M[i,j]這裡的意義有些不一樣,M[i,j]表示能否用第1…i-1個整數找到和為j的方案。如果可以就是1,不能就為0。那樣這個M[i,j]可以表示為:M[i,j] = M[i-1,j] || M[i-1,j-Ai] 也就是說對於第i個整數來說,要麼存在不用這個整數的方案M[i-1,j]或者存在方案M[i-i,j-Ai],這第二個方案加上了當年Ai也就可以了。有興趣的話可以實現一下。

2. change-making Problem.這個問題通俗的描述就是你去超市買東西,最後的零錢是75分。你肯定不希望營業員給你75一個1分的硬幣,營業員需要做的事情就是計算出一個給你最少個數硬幣的方案。如果我們假定特定的硬幣營業員都有的話,我們可以把這個問題看成近似的完全揹包問題。不過完全揹包問題的要求是滿足重量的價值儘量大。這裡在於滿足條件的硬幣數量儘可能小。一樣的我們定義一個和完全揹包類似的M[j]來表示找零錢j需要的硬幣數量。那麼M[j] = min { M[j-Ai] 1, 1<=i<=n }這個j取決於比之小的所有M[j-Ai]的最優硬幣數量方案的最小值。除了這裡的max換乘了min。其他的都非常像吧。

 

 其實類似的問題還是有很多,這裡先貼一些出來總結,如果有更好的例子。以後在補充上去,但是現在這種工作的方式讓人真的很舒服^_^