背包问题

1. 0-1背包问题

假设有n件物品和容量为m的背包，已知每件物品的重量及价值，在满足装入背包的物品重量最大的前提下，使得装入物品的总价值最大。 (1) 二维动态规划

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])$

(2) 一维动态规划

$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背包问题的基础上，每个物品的数量均为无限个。

$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背包问题的基础上，每个物品的数量有限。

$dp[j]=max(dp[j],dp[j-k\ast weights[i]]+k\ast 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]; }