【筆記】DP: 0-1 Knapsack (0-1背包問題)

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

分享本文 Share with friends