動態(tài)規(guī)劃入門——傳說中的零一背包問題
完全背包
在之前的文章當(dāng)中，我們闡述了動態(tài)規(guī)劃當(dāng)中狀態(tài)和決策以及狀態(tài)轉(zhuǎn)移的相關(guān)概念。在背包問題當(dāng)中，背包的容量是狀態(tài)，而選擇哪個物品進(jìn)行獲取則是決策，當(dāng)我們制定了一個決策之后，背包會從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)。而動態(tài)規(guī)劃算法就是枚舉所有狀態(tài)和決策，獲得所有的狀態(tài)轉(zhuǎn)移，并且記錄這個過程中每個狀態(tài)能夠獲得的最優(yōu)解。
在之前的文章當(dāng)中，我們先遍歷了所有的決策，然后再枚舉了所有的狀態(tài)，計算在決策下進(jìn)行轉(zhuǎn)移之后得到的結(jié)果。在之前的零一背包問題當(dāng)中，由于我們每個物品只能獲取一個，如果在前面的狀態(tài)執(zhí)行了決策，那么后面的狀態(tài)則不能進(jìn)行相同的決策。這也就是動態(tài)規(guī)劃的后效性，而在完全背包問題當(dāng)中，我們?nèi)サ袅诉@個限制，也就意味著決策之間不再有后效性，一個決策可以重復(fù)應(yīng)用在各個狀態(tài)當(dāng)中。
所以如果你能理解上面這段話，那么整個算法其實非常簡單，幾乎就是零一背包的代碼。只不過我們把其中倒敘遍歷的背包狀態(tài)再”修正“回來。
之前我們?yōu)榱吮苊馕锲返闹貜?fù)獲取，所以采用了倒敘遍歷的方法，如今我們不再對數(shù)量進(jìn)行限制，意味著我們可以自由地采取決策進(jìn)行轉(zhuǎn)移。要做到這點，就是單純的兩重循環(huán)，第一種枚舉決策， 第二重枚舉狀態(tài)，記錄所有轉(zhuǎn)移可能帶來的最優(yōu)解即可。我們來看代碼：
如果你還沒能完全理解其中的邏輯，我們可以對照一下代碼再來理解一下。在第一種循環(huán)當(dāng)中，我們遍歷了所有的物品完全背包問題算法，每一個物品對應(yīng)了一種決策。每一個決策可以應(yīng)用在各個狀態(tài)上，比如第一個物品是6， 15，代表它的體積是6，價值是15。那么我們遍歷所有能夠應(yīng)用這個決策的狀態(tài)，也就是在不超過背包容量的情況下能夠放下的狀態(tài)。顯然對于一個體積是6的物品來說，只有0到4的狀態(tài)可以放下。比如說我們選擇狀態(tài)2，狀態(tài)2放下了這個物品之后，自然會轉(zhuǎn)移到狀態(tài)8，因為體積增加了6。有可能這個決策會使得狀態(tài)8獲得更好的結(jié)果，也有可能不會，如果會的話我們就更新一下狀態(tài)8記錄的值。這個從一個狀態(tài)采取決策到另一個狀態(tài)的過程就是狀態(tài)轉(zhuǎn)移。
完全背包就是零一背包的無限制版，從原理上來說，兩者的思路和做法基本上是一樣的。如果你能理解零一背包，那么完全背包對你來說也一定不在話下。
細(xì)小的優(yōu)化
在完全背包當(dāng)中，由于所有的物品都可以無限獲取。所以我們可以引入一些零一背包不能進(jìn)行的優(yōu)化，比如對于同樣體積的物品而言，我們可以只保留價值最高的物品，將其他的物品過濾掉。這個思路很樸素，我想大家應(yīng)該都能理解。
比如兩個物品體積都是3，一個價值是4，另一個價值是3，我們完全可以忽略價值是3的那一種。因為兩者帶來的狀態(tài)轉(zhuǎn)移是一樣的，但是明顯前者收益更好。而這個優(yōu)化在零一背包當(dāng)中不可行是因為每個物品只有一個，很有可能會出現(xiàn)兩者都要的情況，所以不能簡單地替換。而在完全背包當(dāng)中則沒有這個問題。
多重背包
和零一背包以及完全背包相比，多重背包要難上一些，它的解法也非常多樣。我們今天先來看一些相對比較簡單的方法。
同樣，我們從最簡單的方法開始講起。最簡單的方法當(dāng)然就是將多重背包蛻化成零一背包來解決，比如一個物品最多可以拿N個，我們就把它拆成N種物品，這N種每種物品最多拿一個，相當(dāng)于我們一種物品可以最多拿N個。這個思路應(yīng)該很簡單，大家都能想明白，但是有個很大的問題完全背包問題算法，就是復(fù)雜度。當(dāng)然我們可以根據(jù)背包的體積做一些優(yōu)化，比如當(dāng)物品的數(shù)量很多并且超過了背包容量的時候，我們可以把超過容量的數(shù)量去掉，但是整體的復(fù)雜度還是很高。尤其是當(dāng)我們背包容量很大的時候。
那么，我們怎么來解決這個問題呢？
這里要介紹一個比較通用的算法，這個算法可以用來優(yōu)化很多問題，也是很多算法的思想。它就是二進(jìn)制表示法。這個方法我們在之前的文章當(dāng)中曾經(jīng)講到過，思想非常簡單，但是非常實用。
二進(jìn)制表示法
所謂二進(jìn)制表示法就是將一個int類型的數(shù)表示成二進(jìn)制，整個算法的思想就是這一句話，所以我想大家應(yīng)該都能理解。但是我們?yōu)槭裁匆獙⒁粋€int轉(zhuǎn)成二進(jìn)制，以及轉(zhuǎn)成二進(jìn)制之后怎么樣來優(yōu)化算法，這個才是我們想知道的，也才是算法的核心重點，不要著急，我們一點點來說明。
我們都知道在計算機(jī)系統(tǒng)當(dāng)中都是以二進(jìn)制存儲的所有數(shù)據(jù)，最典型的就是整數(shù)。一個32位的int，可以表示最大21億的整數(shù)。這個都是我們已知的，但是換一個角度來看，一個21億的數(shù)最后用32個二進(jìn)制位就表示了，其實非常驚人。為什么說二進(jìn)制是一個非常偉大的思想？不在于它難，而在于它高效地壓縮了數(shù)據(jù)。
我們進(jìn)一步來看，32個二進(jìn)制位為什么能表示這么大的數(shù)據(jù)呢？因為這32位int表示的數(shù)據(jù)是不一樣的，第0位表示1，第1位表示2，第2位表示4……到了第31位的時候，表示的數(shù)已經(jīng)非常龐大。我們用這32個數(shù)不同的組合來表示不同的數(shù)，換句話說范圍內(nèi)的所有數(shù)最終都變成了這32個數(shù)中若干個的累加。我們寫成公式就是：
這里的 ai 表示的是第i位的系數(shù)，它只有0和1兩個取值。
這個式子大家都熟悉，但是我們把它應(yīng)用在方程當(dāng)中可能很多人就不清楚了。比如說某個函數(shù)如果滿足這樣的性質(zhì): f(a+b) = f(a) + f(b)，如果直接求 f(a+b) 可能很麻煩，或者是開銷很大，我們就可以用 f(a) 和 f(b) 來獲得。同理，我們用在二進(jìn)制上，我們可以得到：
看到了嗎，我們把 f(x) 的值轉(zhuǎn)化成了最多32個值的和，在有些場景當(dāng)中 f(2^i) 是很容易計算的，但是f(x) 很難直接計算，這個時候我們通過二進(jìn)制轉(zhuǎn)化就會很簡單。
同理，累加理解了，累乘也就水到渠成。如果某個函數(shù) f(x) 滿足: f(ab) = f(a) * f(b)，那么我們同樣可以用二進(jìn)制來表達(dá) f(x)：
對于多重背包這個問題，顯然我們滿足的是累加性質(zhì)。也就是說，對于一個較大的x而言，我們可以用若干個子狀態(tài)累加得到。由于 f(a+b) = f(a) + f(b) ，所以我們很容易發(fā)現(xiàn) f(2) = 2f(1)，f(4) = 2f(2)，也就是說這些子狀態(tài)之間彼此存在倍數(shù)關(guān)系。因此我們可以很輕松地計算出這些子狀態(tài)，再根據(jù)x的二進(jìn)制表示來累加求到 f(x) ，而直接計算 f(x) 則困難得多，計算量也大得多。
在這個問題當(dāng)中，函數(shù)f表示的是我們拿取物品的價值。也就是說，某一種物品，假設(shè)最多有n個，并且單個的價值是p，那么我們拿取2個就是2p，拿取4個就是4p，對于所有2的冪個數(shù)的價值都很容易計算。我們需要枚舉這n個物品拿取的情況，我們枚舉的范圍應(yīng)該是[0, n]。我們將n轉(zhuǎn)化成二進(jìn)制之后，可以通過logn個2的冪排列組合的和得到[0, n]當(dāng)中的任意一個數(shù)。那么，我們只需要將2的冪個數(shù)的物品看成是新的物品，這樣，我們可以用新的物品的01組合，來代替原物品拿取0-n的所有情況。
舉個例子，我們有一個物品一共有15個，價值是3，其中15= 2^0 + 2^1 + 2^2 + 2^3，也就是說我們用4個二進(jìn)制位就可以表示1-15這15這數(shù)字。那么我們用4種物品映射這4個二進(jìn)制位之后，就可以用這4種物品的組合來表示獲取1-15個原物品了。也就是說我們把15個價值是3的物品打了四個包，第一個包里有一個，第二個包里有兩個，第三個包里有四個，第四個包里有八個。如果我們要拿3個原物品，相當(dāng)于拿第一和第二個包裹。如果我們要拿5個原物品，相當(dāng)于拿第一個和第三個包裹。這樣我們就把多重背包的問題轉(zhuǎn)化回了零一背包。
我們之前說了，32位二進(jìn)制位就可以表示20億以上的數(shù)，所以雖然我們進(jìn)行二進(jìn)制處理之后物品的數(shù)量會增多一些，但也是非常有限的。我們做個簡單的復(fù)雜度分析，假設(shè)物品的總數(shù)是N，每種物品最多M個，背包的容量是V。如果用樸素的拆分方法，復(fù)雜度是 O(NMV) ，而使用二進(jìn)制拆分的復(fù)雜度是 O()。和前者相比，從M到logM是一個巨大的優(yōu)化，尤其當(dāng)M很大的時候。
最后，還有一個小問題，我們的物品數(shù)量并不一定剛好能分成若干個2的冪的和，這種情況下怎么辦呢？其實也簡單，我們把分剩下的部分單獨打一個包就好了。比如如果物品的數(shù)量是10，10=1+2+4+3，所以最后一個包就是3。雖然我們用1+2也能表示3，但是這并不會影響結(jié)果的正確性。
到這里，多重背包的解法就介紹完了，說了這么多其實也只是介紹了二進(jìn)制表示這個方法而已。理解了這個方法，它就轉(zhuǎn)化成了零一背包。不得不說這個方法實在是非常巧妙，并且除了在背包問題之外，在許多其他問題中也有類似的運用。所以這個方法不建議錯過。
最后，我們來看下代碼，首先我們來看下二進(jìn)制拆分的部分：
進(jìn)行完二進(jìn)制拆分之后，這個問題就轉(zhuǎn)化成了零一背包。我們只需要套用零一背包的代碼就可以了：
通過神乎其神的二進(jìn)制表示法，我們將多重背包問題又還原成了零一背包，不得不說實在是神奇。但二進(jìn)制表示法并不是唯一的方案，我們也可以不用二進(jìn)制來完成這道題。這涉及到一種全新的方法，由于篇幅限制，我們會在下篇文章當(dāng)中和大家一起學(xué)習(xí)。
今天關(guān)于多重背包和完全背包的文章就到這里，如果覺得有所收獲，請順手點個關(guān)注或者轉(zhuǎn)發(fā)吧，你們的舉手之勞對我來說很重要。