【範例】ZeroJudge b131: NOIP2006 2.开心的金明
目錄
【觀念】0-1背包問題
- 每種物品只有一個且不可分割,只能選擇拿或不拿。每種物品的價值為 v,重量為 w。
- 在背包負重有限的情況下,求背包能夠容納的物品的最大價值。
- 暴力枚舉法:有N種物品,每一種都可以選擇拿或不拿,總共有 2N種可能性要考慮。N = 20時,有超過一百萬種組合要考慮。

- DP (Dynamic Programming):建表紀錄目前位置最好的結果,一步一步地考慮狀態轉移。
- 【方法1】
- 建立二維的DP表格,dp[m+1][W+1] (m種物品,背包最大負重W),初始值為 0。
- dp[i+1][j]:考慮到第 i 種物品時,最大負重為 j 的背包,能夠拿取的最大價值。
- 狀態轉移方程:dp[i+1][j] = max(dp[i][j], dp[i][j – w[i]] + v[i]);
- 【方法2】
- 建立一維的DP表格,dp[W+1] (背包最大負重W),初始值為 0。
- 狀態轉移方程:dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
- 注意:範例程式碼的第15行,為了重複利用記憶體,迴圈需逆向執行。
- 【方法3】
- 交互使用兩個一維陣列。

【方法1】二維的DP表格
#include <iostream>
#include <cstring>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, m; //N(<30000)表示总钱数,m(<25)为希望购买物品的个数
cin >> N >> m;
int v[m], w[m]; //v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5)
int dp[m+1][N+1];
for (int i=0; i<m; i++){
cin >> v[i] >> w[i];
}
memset(dp, 0, sizeof(dp));
for (int i=0; i<m; i++){
for (int j=0; j<=N; j++){
if (j < v[i]) {
dp[i+1][j] = dp[i][j];
} else {
dp[i+1][j] = max(dp[i][j], dp[i][j - v[i]] + v[i] * w[i]);
}
}
}
cout << dp[m][N] << '\n';
return 0;
}
【方法2】一維的DP陣列
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int N, m;
cin >> N >> m;
int v[m], w[m];
for (int i=0; i<m; i++){
cin >> v[i] >> w[i];
}
int dp[N+1];
memset(dp, 0, sizeof(dp));
for (int i=0; i<m; i++){
for (int j=N; j>=v[i]; j--){
dp[j] = max(dp[j], dp[j-v[i]] + v[i]*w[i]);
}
}
cout << dp[N] << '\n';
return 0;
}
【方法3】交互使用兩個一維陣列
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int N, m;
cin >> N >> m;
int v[m], w[m];
for (int i=0; i<m; i++){
cin >> v[i] >> w[i];
}
int dp[2][N+1];
memset(dp, 0, sizeof(dp));
int idx = 0;
for (int i=0; i<m; i++){
for (int j=0; j<=N; j++){
if (j < v[i]) {
dp[idx^1][j] = dp[idx][j];
} else {
dp[idx^1][j] = max(dp[idx][j], dp[idx][j - v[i]] + v[i] * w[i]);
}
}
idx ^= 1;
}
cout << dp[idx][N] << '\n';
return 0;
}
【更多練習】Zerojudge d390: 00562 – Dividing coins 【題解】