背包之01背包、完全背包、多重背包詳解

PS：大家覺得寫得還過得去，就幫我頂博客，謝謝。

首先說下動態規劃，動態規劃這東西就和遞歸一樣，只能找局部關系，若想全部列出來，是很難的，比如漢諾塔。你可以說先把除最后一層的其他所有層都移動到2，再把最后一層移動到3，最后再把其余的從2移動到3，這是一個直觀的關系，但是想列舉出來是很難的，也許當層數n=3時還可以模擬下，再大一些就不可能了，所以，諸如遞歸，動態規劃之類的，不能細想，只能找局部關系。

1.漢諾塔圖片

（引至杭電課件:DP最關鍵的就是狀態，在DP時用到的數組時，也就是存儲的每個狀態的最優值，也就是記憶化搜索）

要了解背包，首先得清楚動態規劃：

動態規劃算法可分解成從先到后的4個步驟：

1. 描述一個最優解的結構；

2. 遞歸地定義最優解的值；

3. 以“自底向上”的方式計算最優解的值；

4. 從已計算的信息中構建出最優解的路徑。

其中步驟1~3是動態規劃求解問題的基礎。如果題目只要求最優解的值，則步驟4可以省略。

背包的基本模型就是給你一個容量為V的背包

在一定的限制條件下放進最多(最少?)價值的東西

當前狀態→ 以前狀態

看了dd大牛的《背包九講》(點擊下載)，迷糊中帶著一絲清醒，這里我也總結下01背包，完全背包，多重背包這三者的使用和區別，部分會引用dd大牛的《背包九講》，如果有錯，歡迎指出。

(www.wutianqi.com留言即可)

首先我們把三種情況放在一起來看：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

比較三個題目，會發現不同點在于每種背包的數量，01背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把這個過程理解下：在前i件物品放進容量v的背包時，

它有兩種情況：

第一種是第i件不放進去，這時所得價值為:f[i-1][v]

第二種是第i件放進去，這時所得價值為：f[i-1][v-c[i]]+w[i]

（第二種是什么意思？就是如果第i件放進去，那么在容量v-c[i]里就要放進前i-1件物品）

最后比較第一種與第二種所得價值的大小，哪種相對大，f[i][v]的值就是哪種。

（這是基礎，要理解?。?/code>

這里是用二位數組存儲的，可以把空間優化，用一位數組存儲。

用f[0..v]表示，f[v]表示把前i件物品放入容量為v的背包里得到的價值。把i從1~n(n件)循環后，最后f[v]表示所求最大值。

*這里f[v]就相當于二位數組的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重點！思考）
首先要知道，我們是通過i從1到n的循環來依次表示前i件物品存入的狀態。即：for i=1..N
現在思考如何能在是f[v]表示當前狀態是容量為v的背包所得價值，而又使f[v]和f[v-c[i]]+w[i]標簽前一狀態的價值？

逆序！

這就是關鍵！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4