【範例】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 【題解】