本文關(guān)鍵詞：0-1背包問題，由筆耕文化傳播整理發(fā)布。

        最近在做背包問題，今天寫點東西總結(jié)一下。

        背包問題，常見的有三種類型：基本的0-1背包、完全背包和多重背包、二維背包 

        首先是基本的0-1背包問題。因為這里的物品一般指花瓶、玉器什么的，要么拿、要么不拿，只有0和1兩種狀態(tài)，所以也叫0-1背包。0-1背包雖然簡單，卻很重要，是“萬法之源”，是其他幾類問題的基礎(chǔ)。 

        初學(xué)者有時會認(rèn)為，0-1背包可以這樣求解：計算每個物品的Vi/Wi，然后依據(jù)Vi/Wi的值，對所有的物品從大到小進(jìn)行排序。其實這種貪心方法是錯誤的。如下表，有三件物品，背包的最大負(fù)重量是50，求可以取得的最大價值。 

        其實，0-1背包是DP的一個經(jīng)典實例，可以用動態(tài)規(guī)劃求解。

DP求解過程可以這樣理解：對于前i件物品，背包剩余容量為j時，所取得的最大價值（此時稱為狀態(tài)3）只依賴于兩個狀態(tài)。

狀態(tài)1：前i-1件物品，背包剩余容量為j。在該狀態(tài)下，只要不選第i個物品，就可以轉(zhuǎn)換到狀態(tài)3。

狀態(tài)2：前i-1件物品，背包剩余容量為j-w[i]。在該狀態(tài)下，選第i個物品，也可以轉(zhuǎn)換到狀態(tài)3。

因為，這里要求最大價值，所以只要從狀態(tài)1和狀態(tài)2中選擇最大價值較大的一個即可。 

狀態(tài)轉(zhuǎn)換方程：

dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-w[i] ) + v[i] )

dp( i,j )表示前i件物品，背包剩余容量為j時，所取得的最大價值。 

        還是結(jié)合上面的例子來說明吧。有三件物品，背包的最大負(fù)重量是50，求可以取得的最大價值。下圖表示了DP自上而下的求解過程。

編程實現(xiàn)：

       一般來說，有了狀態(tài)方程，直接編程實現(xiàn)就game over。dp( i,j )，用一個二維數(shù)組來實現(xiàn)，然后用一個兩層循環(huán)就可以了。不過，有時選擇的物品很多，，背包的容量很大，這時要用二維數(shù)組往往是不現(xiàn)實的。這里有一個方法，可以進(jìn)行空間壓縮，然后使用一維數(shù)組實現(xiàn)。

       還是結(jié)合上面的例子，有三件物品，背包的最大負(fù)重量是5，求可以取得的最大價值。為了方面說明，物品weight依次為：1，2，3。二維數(shù)組下的求解順序，物品數(shù)1--->n, 背包容量1--->w。如圖，要使用一維數(shù)組，背包容量要采用倒序，即w--->1, 只有這樣對于方程dp( j ) = Max( dp( j ), dp (j-w[i] ) + v[i] )，才能達(dá)到等式左邊才表示i,而等式右邊表示i-1的效果。POJ對于題目：3624。下面附代碼。

        完全背包和多重背包。有了基本的0-1背包基礎(chǔ)，下面的東西也就好理解了。 完全背包，指每個物品有無限多個。 多重背包，指每個物品的數(shù)量是有限的。當(dāng)然，這時的問題不再是拿與不拿，而是拿多少的問題，當(dāng)然不能超過背包容量。 

狀態(tài)轉(zhuǎn)換方程：

dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-k*w[i]) + k*v[i] ) ( 0 <= k <= c/ w[i] )

編碼實現(xiàn)：

如果直接編碼，用三層循環(huán)，往往會超時。這樣有一種很有效的壓縮方式：二進(jìn)制壓縮。把原來的物品按照2的n次方進(jìn)行重新組合。用1、2、4、8…進(jìn)行組合，可以組合出任意的數(shù)字。POJ題目：1276

POJ3624

  本文關(guān)鍵詞：0-1背包問題，由筆耕文化傳播整理發(fā)布。