目錄

一、0-1背包問題

二、問題分析

1、確定備忘錄的具體含義

2、狀態(tài)轉(zhuǎn)移方程

3、初始化

4、遍歷順序及輸出

5、回溯法求解最大價值時的背包物品?

三、總結(jié)?

四、完整代碼

一、0-1背包問題

給定種物品（每種物品均只有一個）和一背包。物品i的重量是，其價值為，背包的最大容量為。怎樣選擇裝入背包中的物品，使得其總價值最大？

例如：現(xiàn)有4種物品，其對應(yīng)的重量和價值如圖所示，另有一最大容量為5的背包，求該背包所能裝下物品的最大價值？

物品	?重量	價值
0	2	4
1	1	3
2	4	6
3	3	5

二、問題分析

1、確定備忘錄的具體含義

dp[i][j]:任取第0~i件物品，放入容量為j的背包，能得到的最大價值 例：dp[1][2]=3的含義:任取物品0~物品1，放入容量為2的背包，能得到的最大價值（取物品1放入背包，其價值最大，為3）

dp[i][j] 的定義十分重要，狀態(tài)方程的書寫、數(shù)組初始化、遍歷順序和輸出結(jié)果都必須嚴(yán)格按照該定義進(jìn)行書寫

2、狀態(tài)轉(zhuǎn)移方程

對于物品，它只有放與不放兩種狀態(tài)，當(dāng)它能放入背包時，狀態(tài)轉(zhuǎn)移方程只需取兩種狀態(tài)的最大值; 否則，取不放入時的最大價值。

if (j < w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

?3、初始化

從狀態(tài)轉(zhuǎn)移方程可知，欲求dp[i][j],需先確定dp[i-1][j]和dp[i-1][j-w[i]]的值（即需保證dp[i][j]的左上角數(shù)據(jù)已經(jīng)處理完成），故我們需對第0行和第0列進(jìn)行初始化.

//初始化第0列（即背包容量為0） for (i = 0; i < n; i++)dp[i][0] = 0; //初始化第0行（即只有物品0） for (j = 1; j <= max_weight; j++) {if (w[0] <= j) dp[0][j] = v[0];elsedp[0][j] = 0; }

4、遍歷順序及輸出

遍歷順序：求解dp[i][j]只需提前知道其左上角的數(shù)據(jù)，故以下兩種遍歷方式均可。

1、先遍歷背包再遍歷物品（即物品數(shù)固定，背包容量逐增至最大，物品再加1）

?2、先遍歷物品再遍歷背包（即背包容量固定，物品數(shù)逐增至最大，背包容量再加1）

輸出：dp[n-1][max_weight]: n件物品任取，放入容量為max_weight的背包，所得的最大價值。

//先遍歷物品再遍歷背包 for (i = 1; i < n; i++) { //遍歷物品for (j = 1; j <= max_weight; j++) { //遍歷背包if (j < w[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);} } //先遍歷背包再遍歷物品 for (j = 1; j <= max_weight; j++) { //遍歷背包for (i = 1; i < n; i++) { //遍歷物品if (j < w[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);} }

5、求解最大價值時的背包物品?

由狀態(tài)轉(zhuǎn)移方程（dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])）可知，當(dāng)dp[i][j]dp[i-1][j]時，物品i被放入背包中（判斷條件），當(dāng)dp[i][j]=0時，背包中已經(jīng)沒有物品（結(jié)束條件）。

//回溯法求解裝入物品 i--; j--; //循環(huán)結(jié)束后,i=n,j=max_weight+1,故使用dp[n - 1][max_weight]須自減1 cout << "最大價值時的背包物品為：" << endl; while (dp[i][j]&&i>=0) { if (dp[i][j] != dp[i - 1][j]) {cout << "物品" << i << endl;j -= w[i]; //裝入物品i后背包的最大容量}i--; //物品i已經(jīng)處理完成，接下來討論物品i-1 }

1、 使用dp[i][j]（最大價值)前一定要對i,j進(jìn)行處理，否則，運(yùn)行時會拋出異常；

2、結(jié)束條件一定要加上i>=0,否則，運(yùn)行結(jié)果可能會出現(xiàn)物品-1等錯誤。

3、該法得到的結(jié)果只為其中的一組最優(yōu)解，可能還存在其他最優(yōu)解，例如：當(dāng)我們裝入物品0（2，4）和物品3（3，5）時，其最大價值也為9.

三、總結(jié)?

?1、0-1背包問題是背包問題的基礎(chǔ)。深入了解0-1背包問題（每件物品只有一個）是掌握完全背包問題（每件物品有無數(shù)個）、多重背包問題（不同物品數(shù)量不同）和分組背包（物品分為多組，每組最多選一個）的關(guān)鍵；

2、使用dp[i][j]數(shù)組時，一定要注意數(shù)組的界限問題，避免越界訪問造成錯誤。比如：剛開始的時候，我認(rèn)為背包不存在容量為0的情況，故沒有將第一列初始化為0，導(dǎo)致輸出出錯，將dp[i][j]全部打印出來后，才知道是dp[1][1]出錯了，因?yàn)閐p[1][1]=max(dp[0][1],dp[0][0]+v[0])，需要用到dp[0][0]，造成越界。所以，檢驗(yàn)算法的正確性，可以先人工求解出dp[i][j]數(shù)組，再用程序?qū)⑵浯蛴〕鰜?#xff0c;這樣有利于我們快速找到問題所在。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 轉(zhuǎn)換表（打印）

轉(zhuǎn)換表(人工）
	0	1	2	3	4	5
0	0	0	4	4	4	4
1	0	3	4	7	7	7
2	0	3	4	7	7	9
3	0	3	4	7	8	9

3、背包問題一定要先明確輔助數(shù)組的具體含義再確定轉(zhuǎn)換方程，根據(jù)轉(zhuǎn)換方程來確定初始化、遍歷順序和輸出結(jié)果。

四、完整代碼

#include<iostream> #include<algorithm> using namespace std;const int max_weight = 5; const int n = 4;int main() {int i, j;int w[n] = { 2,1,4,3 }; //重量int v[n] = { 4,3,6,5 }; //價值int dp[n][max_weight+1];//輔助數(shù)組//初始化第0列（即背包容量為0）for (i = 0; i < n; i++)dp[i][0] = 0;//初始化第0行（即只有物品0）for (j = 1; j <= max_weight; j++) {if (w[0] <= j) dp[0][j] = v[0];elsedp[0][j] = 0;}//狀態(tài)轉(zhuǎn)移//先遍歷物品再遍歷背包for (i = 1; i < n; i++) { //遍歷物品for (j = 1; j <= max_weight; j++) { //遍歷背包if (j < w[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);}}//輸出cout << dp[n - 1][max_weight] << endl;//回溯法求解裝入物品i--; j--; //循環(huán)結(jié)束后,i=n,j=max_weight+1,故使用dp[n - 1][max_weight]須自減1cout << "最大價值時的背包物品為：" << endl;while (dp[i][j]&&i>=0) { if (dp[i][j] != dp[i - 1][j]) {cout << "物品" << i << endl;j -= w[i]; //裝入物品i后背包的最大容量}i--; //物品i已經(jīng)處理完成，接下來討論物品i-1}return 0; }

運(yùn)行結(jié)果：?

總結(jié)

以上是生活随笔為你收集整理的【动态规划】01背包问题+查找背包物品的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。