動態規劃算法——詳解完全揹包與多重揹包問題

今天是算法數據結構專題的第13篇文章，也是動態規劃專題的第二篇。

上一講當中我們一起學習了動態規劃算法中的零一揹包問題，我們知道了所謂的零一揹包是指每一種物品只有一個，所以它的狀態只有0和1兩種，即拿或者不拿。而今天我們要來討論物品不止有一個的情況，物品不止有一個也分兩種，一種是不作任何限制，要多少有多少，這種稱為完全揹包問題，另一種是依然有個數限制，這種稱為多重揹包問題。

我們一個一個來看，我們先從其中比較簡單的完全揹包開始。由於我們這是一個連續的專題，沒有看過上篇文章或者是新關注的同學可以移步我們專題的第一篇：

完全揹包

在之前的文章當中，我們闡述了動態規劃當中狀態和決策以及狀態轉移的相關概念。在揹包問題當中，揹包的容量是狀態，而選擇哪個物品進行獲取則是決策，當我們制定了一個決策之後，揹包會從一個狀態轉移到另一個狀態。而動態規劃算法就是枚舉所有狀態和決策，獲得所有的狀態轉移，並且記錄這個過程中每個狀態能夠獲得的最優解。

在之前的文章當中，我們先遍歷了所有的決策，然後再枚舉了所有的狀態，計算在決策下進行轉移之後得到的結果。在之前的零一揹包問題當中，由於我們每個物品只能獲取一個，如果在前面的狀態執行了決策，那麼後面的狀態則不能進行相同的決策。這也就是動態規劃的

所以如果你能理解上面這段話，那麼整個算法其實非常簡單，幾乎就是零一揹包的代碼。只不過我們把其中倒敘遍歷的揹包狀態再”修正“回來。

之前我們為了避免物品的重複獲取，所以採用了倒敘遍歷的方法，如今我們不再對數量進行限制，意味著我們可以自由地採取決策進行轉移。要做到這點，就是單純的兩重循環，第一種枚舉決策， 第二重枚舉狀態，記錄所有轉移可能帶來的最優解即可。我們來看代碼：

如果你還沒能完全理解其中的邏輯，我們可以對照一下代碼再來理解一下。在第一種循環當中，我們遍歷了所有的物品，每一個物品對應了一種決策。每一個決策可以應用在各個狀態上，比如第一個物品是6， 15，代表它的體積是6，價值是15。那麼我們遍歷所有能夠應用這個決策的狀態，也就是在不超過揹包容量的情況下能夠放下的狀態。顯然對於一個體積是6的物品來說，只有0到4的狀態可以放下。比如說我們選擇狀態2，狀態2放下了這個物品之後，自然會轉移到狀態8，因為體積增加了6。有可能這個決策會使得狀態8獲得更好的結果，也有可能不會，如果會的話我們就更新一下狀態8記錄的值。這個從一個狀態採取決策到另一個狀態的過程就是狀態轉移。

完全揹包就是零一揹包的無限制版，從原理上來說，兩者的思路和做法基本上是一樣的。如果你能理解零一揹包，那麼完全揹包對你來說也一定不在話下。

細小的優化

在完全揹包當中，由於所有的物品都可以無限獲取。所以我們可以引入一些零一揹包不能進行的優化，比如對於同樣體積的物品而言，我們可以只保留價值最高的物品，將其他的物品過濾掉。這個思路很樸素，我想大家應該都能理解。

比如兩個物品體積都是3，一個價值是4，另一個價值是3，我們完全可以忽略價值是3的那一種。因為兩者帶來的狀態轉移是一樣的，但是明顯前者收益更好。而這個優化在零一揹包當中不可行是因為每個物品只有一個，很有可能會出現兩者都要的情況，所以不能簡單地替換。而在完全揹包當中則沒有這個問題。

多重揹包

和零一揹包以及完全揹包相比，多重揹包要難上一些，它的解法也非常多樣。我們今天先來看一些相對比較簡單的方法。

同樣，我們從最簡單的方法開始講起。最簡單的方法當然就是將多重揹包蛻化成零一揹包來解決，比如一個物品最多可以拿N個，我們就把它拆成N種物品，這N種每種物品最多拿一個，相當於我們一種物品可以最多拿N個。這個思路應該很簡單，大家都能想明白，但是有個很大的問題，就是複雜度。當然我們可以根據揹包的體積做一些優化，比如當物品的數量很多並且超過了揹包容量的時候，我們可以把超過容量的數量去掉，但是整體的複雜度還是很高。尤其是當我們揹包容量很大的時候。

那麼，我們怎麼來解決這個問題呢？

這裡要介紹一個比較通用的算法，這個算法可以用來優化很多問題，也是很多算法的思想。它就是

二進制表示法

所謂二進制表示法就是將一個int類型的數表示成二進制，整個算法的思想就是這一句話，所以我想大家應該都能理解。但是我們為什麼要將一個int轉成二進制，以及轉成二進制之後怎麼樣來優化算法，這個才是我們想知道的，也才是算法的核心重點，不要著急，我們一點點來說明。

我們都知道在計算機系統當中都是以二進制存儲的所有數據，最典型的就是整數。一個32位的int，可以表示最大21億的整數。這個都是我們已知的，但是換一個角度來看，一個21億的數最後用32個二進制位就表示了，其實非常驚人。為什麼說二進制是一個非常偉大的思想？不在於它難，而在於它高效地壓縮了數據。

我們進一步來看，32個二進制位為什麼能表示這麼大的數據呢？因為這32位int表示的數據是不一樣的，第0位表示1，第1位表示2，第2位表示4……到了第31位的時候，表示的數已經非常龐大。我們用這32個數不同的組合來表示不同的數，換句話說範圍內的所有數最終都變成了這32個數中若干個的累加。我們寫成公式就是：

這裡的 ai 表示的是第i位的係數，它只有0和1兩個取值。

這個式子大家都熟悉，但是我們把它應用在方程當中可能很多人就不清楚了。比如說某個函數如果滿足這樣的性質: f(a+b) = f(a) + f(b)，如果直接求 f(a+b) 可能很麻煩，或者是開銷很大，我們就可以用 f(a) 和 f(b) 來獲得。同理，我們用在二進制上，我們可以得到：

看到了嗎，我們把 f(x) 的值轉化成了最多32個值的和，在有些場景當中 f(2^i) 是很容易計算的，但是f(x) 很難直接計算，這個時候我們通過二進制轉化就會很簡單。

同理，累加理解了，累乘也就水到渠成。如果某個函數 f(x) 滿足: f(ab) = f(a) * f(b)，那麼我們同樣可以用二進制來表達 f(x)：

對於多重揹包這個問題，顯然我們滿足的是累加性質。也就是說，對於一個較大的x而言，我們可以用若干個子狀態累加得到。由於 f(a+b) = f(a) + f(b) ，所以我們很容易發現 f(2) = 2f(1)，f(4) = 2f(2)，也就是說這些子狀態之間彼此存在倍數關係。因此我們可以很輕鬆地計算出這些子狀態，再根據x的二進制表示來累加求到 f(x) ，而直接計算 f(x) 則困難得多，計算量也大得多。

在這個問題當中，函數f表示的是我們拿取物品的價值。也就是說，某一種物品，假設最多有n個，並且單個的價值是p，那麼我們拿取2個就是2p，拿取4個就是4p，對於所有2的冪個數的價值都很容易計算。我們需要枚舉這n個物品拿取的情況，我們枚舉的範圍應該是[0, n]。我們將n轉化成二進制之後，可以通過logn個2的冪排列組合的和得到[0, n]當中的任意一個數。那麼，我們只需要將2的冪個數的物品看成是新的物品，這樣，我們可以用新的物品的01組合，來代替原物品拿取0-n的所有情況。

舉個例子，我們有一個物品一共有15個，價值是3，其中15= 2^0 + 2^1 + 2^2 + 2^3，也就是說我們用4個二進制位就可以表示1-15這15這數字。那麼我們用4種物品映射這4個二進制位之後，就可以用這4種物品的組合來表示獲取1-15個原物品了。也就是說我們把15個價值是3的物品打了四個包，第一個包裡有一個，第二個包裡有兩個，第三個包裡有四個，第四個包裡有八個。如果我們要拿3個原物品，相當於拿第一和第二個包裹。如果我們要拿5個原物品，相當於拿第一個和第三個包裹。這樣我們就把多重揹包的問題轉化回了零一揹包。

我們之前說了，32位二進制位就可以表示20億以上的數，所以雖然我們進行二進制處理之後物品的數量會增多一些，但也是非常有限的。我們做個簡單的複雜度分析，假設物品的總數是N，每種物品最多M個，揹包的容量是V。如果用樸素的拆分方法，複雜度是 O(NMV) ，而使用二進制拆分的複雜度是 O(NlogMV)。和前者相比，從M到logM是一個巨大的優化，尤其當M很大的時候。

最後，還有一個小問題，我們的物品數量並不一定剛好能分成若干個2的冪的和，這種情況下怎麼辦呢？其實也簡單，我們把分剩下的部分單獨打一個包就好了。比如如果物品的數量是10，10=1+2+4+3，所以最後一個包就是3。雖然我們用1+2也能表示3，但是這並不會影響結果的正確性。

到這裡，多重揹包的解法就介紹完了，說了這麼多其實也只是介紹了二進制表示這個方法而已。理解了這個方法，它就轉化成了零一揹包。不得不說這個方法實在是非常巧妙，並且除了在揹包問題之外，在許多其他問題中也有類似的運用。所以這個方法不建議錯過。

最後，我們來看下代碼，首先我們來看下二進制拆分的部分：

進行完二進制拆分之後，這個問題就轉化成了零一揹包。我們只需要套用零一揹包的代碼就可以了：

通過神乎其神的二進制表示法，我們將多重揹包問題又還原成了零一揹包，不得不說實在是神奇。但

今天關於多重揹包和完全揹包的文章就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。

閱讀更多 承志的算法課堂 的文章

關鍵字: 算法 物品 數據結構