動态規劃求解背包問題

背包問題

1. 0-1背包問題

假設有n件物品和容量為m的背包，已知每件物品的重量及價值，在滿足裝入背包的物品重量最大的前提下，使得裝入物品的總價值最大。

(1) 二維動态規劃

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t s [ i ] ] + v a l u e s [ i ] ) dp[i][j]=max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−weights[i]]+values[i])

(2) 一維動态規劃

d p [ j ] = m a x ( d p [ j ] , d p [ j − w e i g h t s [ i ] ] + v a l u e s [ i ] ) dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) dp[j]=max(dp[j],dp[j−weights[i]]+values[i])

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//二維動态規劃
int knapsack2(int n, int m, vector<int> &weights, vector<int> &values) {
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (weights[i] > j) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
		}
	}
	return dp[n][m];
}

//一維動态規劃
int knapsack1(int n, int m, vector<int> &weights, vector<int> &values) {
	vector<int> dp(m + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= weights[i]; j--) {
			dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
		}
	}
	return dp[m];
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> weights(n + 1, 0);
	vector<int> values(n + 1, 0);
	for (int i = 1; i <= n; i++) cin >> weights[i];
	for (int i = 1; i <= n; i++) cin >> values[i];
	cout << knapsack1(n, m, weights, values) << endl;
	//cout << knapsack2(n, m, weights, values) << endl;
}
           

2. 完全背包問題

在0-1背包問題的基礎上，每個物品的數量均為無限個。

d p [ j ] = m a x ( d p [ j ] , d p [ j − w e i g h t s [ i ] ] + v a l u e s [ i ] ) dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) dp[j]=max(dp[j],dp[j−weights[i]]+values[i])

int knapsack3(int n, int m, vector<int> &weights, vector<int> &values) {
	vector<int> dp(m + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = weights[i]; j <= m; j++) {
			dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
		}
	}
	return dp[m];
}
           

3. 多重背包問題

在0-1背包問題的基礎上，每個物品的數量有限。

d p [ j ] = m a x ( d p [ j ] , d p [ j − k ∗ w e i g h t s [ i ] ] + k ∗ v a l u e s [ i ] ) dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i]) dp[j]=max(dp[j],dp[j−k∗weights[i]]+k∗values[i])

int knapsack4(int n, int m, vector<int> &weights, vector<int> &values, vector<int> &nums) {
	vector<int> dp(m + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= weights[i]; j--) {
			for (int k = 0; k <= nums[i]; k++) {
				if (j - k * weights[i] < 0) break;
				dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i]);
			}
		}
	}
	return dp[m];
}