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

PS：大家覺(jué)得寫(xiě)得還過(guò)得去，就幫我把博客頂一下，謝謝。

首先說(shuō)下動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃這東西就和遞歸一樣，只能找局部關(guān)系，若想全部列出來(lái)，是很難的，比如漢諾塔。你可以說(shuō)先把除最后一層的其他所有層都移動(dòng)到2，再把最后一層移動(dòng)到3，最后再把其余的從2移動(dòng)到3，這是一個(gè)直觀(guān)的關(guān)系，但是想列舉出來(lái)是很難的，也許當(dāng)層數(shù)n=3時(shí)還可以模擬下，再大一些就不可能了，所以，諸如遞歸，動(dòng)態(tài)規(guī)劃之類(lèi)的，不能細(xì)想，只能找局部關(guān)系。

1.漢諾塔圖片

（引至杭電課件:DP最關(guān)鍵的就是狀態(tài)，在DP時(shí)用到的數(shù)組時(shí)，也就是存儲(chǔ)的每個(gè)狀態(tài)的最優(yōu)值，也就是記憶化搜索）

要了解背包，首先得清楚動(dòng)態(tài)規(guī)劃：

動(dòng)態(tài)規(guī)劃算法可分解成從先到后的4個(gè)步驟：

1. 描述一個(gè)最優(yōu)解的結(jié)構(gòu)；

2. 遞歸地定義最優(yōu)解的值；

3. 以“自底向上”的方式計(jì)算最優(yōu)解的值；

4. 從已計(jì)算的信息中構(gòu)建出最優(yōu)解的路徑。

其中步驟1~3是動(dòng)態(tài)規(guī)劃求解問(wèn)題的基礎(chǔ)。如果題目只要求最優(yōu)解的值，則步驟4可以省略。

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

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

當(dāng)前狀態(tài)→ 以前狀態(tài)

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

(www.wutianqi.com留言即可)

首先我們把三種情況放在一起來(lái)看：

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

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

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

比較三個(gè)題目，會(huì)發(fā)現(xiàn)不同點(diǎn)在于每種背包的數(shù)量，01背包是每種只有一件，完全背包是每種無(wú)限件，而多重背包是每種有限件。

——————————————————————————————————————————————————————————–

先來(lái)分析01背包：

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

這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。

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

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

把這個(gè)過(guò)程理解下：在前i件物品放進(jìn)容量v的背包時(shí)，

它有兩種情況：

第一種是第i件不放進(jìn)去，這時(shí)所得價(jià)值為:f[i-1][v]

第二種是第i件放進(jìn)去，這時(shí)所得價(jià)值為：f[i-1][v-c[i]]+w[i]

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

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

（這是基礎(chǔ)，要理解！）

這里是用二位數(shù)組存儲(chǔ)的，可以把空間優(yōu)化，用一位數(shù)組存儲(chǔ)。

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

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

逆序！

這就是關(guān)鍵！

1
            2
            3
            

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

分析上面的代碼：當(dāng)內(nèi)循環(huán)是逆序時(shí)，就可以保證后一個(gè)f[v]和f[v-c[i]]+w[i]是前一狀態(tài)的！
這里給大家一組測(cè)試數(shù)據(jù)：

測(cè)試數(shù)據(jù)：
10,3
3,4
4,5
5,6

這個(gè)圖表畫(huà)得很好，借此來(lái)分析：

C[v]從物品i=1開(kāi)始，循環(huán)到物品3，期間，每次逆序得到容量v在前i件物品時(shí)可以得到的最大值。（請(qǐng)?jiān)诓莞寮埳献约寒?huà)一畫(huà)）

這里以一道題目來(lái)具體看看：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代碼在這里：http://www.wutianqi.com/?p=533

分析：

具體根據(jù)上面的解釋以及我給出的代碼分析。這題很基礎(chǔ)，看懂上面的知識(shí)應(yīng)該就會(huì)做了。

——————————————————————————————————————————————————————————–

完全背包：

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

完全背包按其思路仍然可以用一個(gè)二維數(shù)組來(lái)寫(xiě)出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同樣可以轉(zhuǎn)換成一維數(shù)組來(lái)表示：

偽代碼如下：

1
            2
            3
            

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

順序！

想必大家看出了和01背包的區(qū)別，這里的內(nèi)循環(huán)是順序的，而01背包是逆序的。
現(xiàn)在關(guān)鍵的是考慮：為何完全背包可以這么寫(xiě)？
在次我們先來(lái)回憶下，01背包逆序的原因？是為了是max中的兩項(xiàng)是前一狀態(tài)值，這就對(duì)了。
那么這里，我們順序?qū)懀@里的max中的兩項(xiàng)當(dāng)然就是當(dāng)前狀態(tài)的值了，為何？
因?yàn)槊糠N背包都是無(wú)限的。當(dāng)我們把i從1到N循環(huán)時(shí)，f[v]表示容量為v在前i種背包時(shí)所得的價(jià)值，這里我們要添加的不是前一個(gè)背包，而是當(dāng)前背包。所以我們要考慮的當(dāng)然是當(dāng)前狀態(tài)。
這里同樣給大家一道題目：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代碼：http://www.wutianqi.com/?p=535

（分析代碼也是學(xué)習(xí)算法的一種途徑，有時(shí)并不一定要看算法分析，結(jié)合題目反而更容易理解。）

——————————————————————————————————————————————————————————–

多重背包

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

這題目和完全背包問(wèn)題很類(lèi)似。基本的方程只需將完全背包問(wèn)題的方程略微一改即可，因?yàn)閷?duì)于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

這里同樣轉(zhuǎn)換為01背包：

普通的轉(zhuǎn)換對(duì)于數(shù)量較多時(shí)，則可能會(huì)超時(shí)，可以轉(zhuǎn)換成二進(jìn)制（暫時(shí)不了解，所以先不講）

對(duì)于普通的。就是多了一個(gè)中間的循環(huán)，把j=0~bag[i]，表示把第i中背包從取0件枚舉到取bag[i]件。

給出一個(gè)例題：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

代碼：http://www.wutianqi.com/?p=537

因?yàn)橄抻趥€(gè)人的能力，我只能講出個(gè)大概，請(qǐng)大家具體還是好好看看dd大牛的《背包九講》。

暫時(shí)講完后，隨著以后更深入的了解，我會(huì)把資料繼續(xù)完善，供大家一起學(xué)習(xí)探討。(我的博客：www.wutianqi.com如果大家有問(wèn)題或者資料里的內(nèi)容有錯(cuò)誤，可以留言給出，謝謝您的支持。)

原文下載地址：（Word版）
http://download.csdn.net/source/2587577