0-1 背包問題：給定 n 種物品和一個容量為 C 的背包，物品 i 的重量是 wi，其價值為 vi 。
問：應該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？
分析一波：面對每個物品，我們隻有選擇拿取或者不拿兩種選擇，不能選擇裝入某物品的一部分，也不能裝入同一物品多次。
解決辦法：聲明一個 大小為 m[n][c]（表示目前總價值） 的二維數組，m[ i ][ j ] 表示 在面對第 i 件物品，且背包容量為 j（沒裝任何物品時的容量，假設背包就那麼大，隻有容量 j ）
（1）j < w[i] 的情況，這時候背包容量不足以放下第 i 件物品，隻能選擇不拿
m[ i ][ j ] = m[ i-1 ][ j ] （不拿物品時，價值等于考慮第 i-1 件時的價格）
（2）j>=w[i] 的情況，這時背包容量可以放下第 i 件物品，我們就要考慮拿這件物品是否能擷取更大的價值。
如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] + v[ i ]。 這裡的m[ i-1 ][ j-w[ i ] ]指的就是考慮了i-1件物品，背包容量為j-w[i]時的最大價值，也是相當于為第i件物品騰出了w[i]的空間。
如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）
究竟是拿還是不拿，自然是比較這兩種情況那種價值最大。
由此可以得到狀态轉移方程：
if(j>=w[i])
m[i][j]=max( m[i-1][j], m[i-1][j-w[i]]+v[i] );
else
m[i][j]=m[i-1][j]; 例：0-1背包問題。在使用動态規劃算法求解0-1背包問題時，使用二維數組m[i][j]存儲，m[i][j]數組值表示價值，背包容量為j，可選物品為i、i+1、……、n時0-1背包問題的最優值。繪制
價值數組v = {8, 10, 6, 3, 7, 2}，
重量數組w = {4, 6, 2, 2, 5, 1}，
背包容量C = 12時對應的m[i][j]數組。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| 1 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | |||
| 2 | 8 | 8 | 10 | 10 | 10 | 10 | 18 | 18 | 18 | |||
| 3 | 6 | 6 | 8 | 8 | 14 | 14 | 16 | 16 | 18 | 18 | 24 | |
| 4 | 6 | 6 | 9 | 9 | 14 | 14 | 17 | 17 | 19 | 19 | 24 | |
| 5 | 6 | 6 | 9 | 9 | 14 | 14 | 17 | 17 | 19 | 21 | 24 | |
| 6 | 2 | 6 | 8 | 9 | 11 | 14 | 16 | 17 | 19 | 19 | 21 | 24 |
(第一行和第一列為序号，其數值為0)
如m[2][6],在面對第2件物品，背包容量為6時，
我們可以選擇不拿，那麼獲得價值僅為第一件物品的價值8。
即：m[ 2 ][ 6 ] = m[1 ][ 6 ] （m[ i ][ j ] = m[ i-1 ][ j ]）
如果拿，就要把第一件物品拿出來，放第二件物品，價值10，那我們當然是選擇拿。
即：m[2][6] = m[2-1][6-6]+10 =0+10 = 10（m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]）
依次類推，得到m[6][12]就是考慮所有物品，背包容量為C時的最大價值。
#include <iostream>
using namespace std;
const int N=15;
int main() {
int v[N]={0,8,10,6,3,7,2};//注意這裡多了一個前導0
int w[N]={0,4,6,2,2,5,1};
int m[N][N];
int n=6,c=12;
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++) { //注意前導第0列元素為0
for(int j=1;j<=c;j++) {
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); //最優子結構
else
m[i][j]=m[i-1][j];
}
}
for(int i=1;i<=n;i++) { //輸出序列
for(int j=1;j<=c;j++) {
cout<<m[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
0 0 0 8 8 8 8 8 8 8 8 8
0 0 0 8 8 10 10 10 10 18 18 18
0 6 6 8 8 14 14 16 16 18 18 24
0 6 6 9 9 14 14 17 17 19 19 24
0 6 6 9 9 14 14 17 17 19 21 24
2 6 8 9 11 14 16 17 19 19 21 24 到這一步，可以确定的是可能獲得的最大價值，但是我們并不清楚具體選擇哪幾樣物品能獲得最大價值。
另起一個 x[ ] 數組，x[i]=0表示不拿，x[i]=1表示拿。
m[n][c]為最優值，如果m[n][c]=m[n-1][c] ,說明有沒有第n件物品都一樣，則x[n]=0 ; 否則 x[n]=1。當x[n]=0時，由x[n-1][c]繼續構造最優解；當x[n]=1時，則由x[n-1][c-w[i]]繼續構造最優解。以此類推，可構造出所有的最優解。
例：
[cpp]
view plain
copy
1. void traceback()
2. {
3. for(int i=n;i>1;i--) //注意這裡是2-n，沒有處理i=1
4. {
5. if(m[i][c]==m[i-1][c])
6. x[i]=0; //沒拿
7. else
8. {
9. x[i]=1; //拿了
10. c-=w[i];
11. }
12. }
13. x[1]=(m[1][c]>0)?1:0; //這裡處理i=1
14. } 某工廠預計明年有A、B、C、D四個建立項目，每個項目的投資額Wk及其 投資後的收益Vk 如下表所示，投資總額為30萬元，如何選擇項目才能使總收益最大？
| Project項目 | Wk投資額 | Vk收益 |
| A | 15 | 12 |
| B | 10 | 8 |
| C | 12 | 9 |
| D | 8 | 5 |
結合前面兩段代碼
1. #include <iostream>
2. #include <cstring>
3. using namespace std;
4.
5. const int N=150;
6.
7. int v[N]={0,12,8,9,5};
8. int w[N]={0,15,10,12,8};
9. int x[N];
10. int m[N][N];
11. int c=30;
12. int n=4;
13. void traceback()
14. {
15. for(int i=n;i>1;i--)
16. {
17. if(m[i][c]==m[i-1][c])
18. x[i]=0;
19. else
20. {
21. x[i]=1;
22. c-=w[i];
23. }
24. }
25. x[1]=(m[1][c]>0)?1:0;
26. }
27.
28. int main()
29. {
30. sizeof(m));
31. for(int i=1;i<=n;i++)
32. {
33. for(int j=1;j<=c;j++)
34. {
35. if(j>=w[i])
36. m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
37. else
38. m[i][j]=m[i-1][j];
39. }
40. }
41. /*
42. for(int i=1;i<=6;i++)
43. {
44. for(int j=1;j<=c;j++)
45. {
46. cout<<m[i][j]<<' ';
47. }
48. cout<<endl;
49. }
50. */
51. traceback();
52. for(int i=1;i<=n;i++)
53. cout<<x[i];
54. return 0;
55. } 輸出x[i]數組：0111，輸出m[4][30]：22。
得出結論：選擇BCD三個項目總收益最大，為22萬元。
不過這種算法隻能得到一種最優解，并不能得出所有的最優解。
其他人解法：空間優化
1. #include<bits/stdc++.h>
2. using namespace std;
3. int dp[1005][1005];
4. int weight[1005];
5. int value[1005];
6. int main()
7. {
8. int n,m;
9. cin>>m>>n;
10. sizeof(dp));//數組清空,其實同時就把邊界給做了清理
11. for(int i=1; i<=n; i++)
12. cin>>weight[i]>>value[i];
13. //從1開始有講究的因為涉及到dp[i-1][j],從0開始會越界
14. for(int i=1; i<=n; i++)//判斷每個物品能否放進
15. {
16. for(int j=0; j<=m; j++)//對每個狀态進行判斷
17. //這邊兩重for都可以倒着寫，隻是需要處理最邊界的情況，滾動數組不一樣
18. {
19. if(j>=weight[i])//能放進
20. dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
21.
22. else dp[i][j]=dp[i-1][j];//不能放進
23. }
24. }
25. cout<<dp[n][m]<<endl;
26. return 0;
27. } 然後啊，我們來仔細分析分析就會發現，這個數組開銷還是很大的，因為是二維的，萬一哪個資料一大，分分鐘記憶體超限，是以有了下邊的解法
傳說中的---------------滾動數組！！！
啊？什麼是滾動數組。
說白了二維數組隻是把每個物品都跑一遍，然後到最後一個物品的時候輸出答案，那麼過程值隻是計算的時候用一次，我沒必要存下來。是以用一個數組去滾動存儲，然後用後一個狀态的值去覆寫前面一個狀态。然後形象的叫它：滾動數組（ma！dan！一點都不形象，我了解了好久）
好吧，假裝很形象。
那麼問題來了，怎麼樣用一維的去代替二維的工作，或者說怎麼去思考。這是一個難點。
那麼我們想，周遊物品的那個for肯定不能省去，然後裡邊的for也不能省。。。。那麼。就把那個i給他删了吧，好像确實沒啥用哦。
然後就出現了這樣的代碼
看上去好像很厲害的樣子,但是這個絕對是錯的，因為第二個for裡存在某個dp[j]被改動過，然後再次影響到更大的j。就像我們再對一個數組進行移位操作，一不小心就全部成了一樣的數。（别笑，你們以前肯定碰到過|||- -）
[cpp]
view plain
copy
1. for(int i=1; i<=n; i++)
2. {
3. for(int j=weight[i]; j<=m; j++)
4. {
5. dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
6. }
7. } 額。。回到正題，上邊的代碼會有重複影響，确實歪打正着的碰上了另一個背包。這個另說，現在附上正确的思路。
[cpp]
view plain
copy
1. #include<bits/stdc++.h>
2. using namespace std;
3. int dp[1005];//滾動數組的寫法，省下空間省不去時間
4. int weight[1005];
5. int value[1005];
6. int main()
7. {
8. int n,m;
9. cin>>m>>n;
10. sizeof(dp));
11. for(int i=1; i<=n; i++)
12. cin>>weight[i]>>value[i];
13. for(int i=1; i<=n; i++)//對每個數判斷，可反
14. {
15. for(int j=m; j>=weight[i]; j--)//這裡這個循環定死，不能反,反了就是完全背包
16. {
17. //其實不斷在判斷最優解，一層一層的
18. }
19. }
20. cout<<dp[m]<<endl;
21. return 0;
22. } ![HDU 6232 Confliction[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)