给定背包容量C=9，给定四个物品与价值，能装入的最大价值是多少？
物品重量w = { 2,3,4,5 };
物品价值v = { 3,4,6,6 };
dp[i][j]表示对前i种物品，背包容量为j能装入的最大价值。
对于第i+1个物品，可以选择装或者不装两种情况
int backpack(vector<int> w, vector<int> v) { int c = 0; cin >> c; int n = w.size(); vector<vector<int>>dp(n, vector<int>(c+1, 0)); for (int i = 1; i < n; i++) { for (int j = 0; j <= c; j++) { if (j - w[i] >= 0) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n - 1][c]; }
完全背包问题
每个物品可以多次选择。
1.贪心算法，计算v[i]/w[i],尽可能多的选择性价比高的物品。
2.动态规划，考虑每个物品选择i个的最优方案
算法思想：用数组dp[i][j]表示考虑前i个物品，背包容量为j情况下所能装下的最大价值量，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-kv[i-1]] + kw[i-1])，0=<kv[i-1] <= j。
k=0时表示装不下第i个物品或者不装第i个物品的情况，而dp[i - 1][j-kv[i-1]] + k*w[i-1]表示能装下第i个物品时，尝试所有可能.
最终结果返回dp[n][c],n表示物品个数，c表示背包容量。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int backpack(vector<int>v, vector<int>w, int c) { int n = v.size();//物品数量 vector<vector<int>> dp(n+1, vector<int>(c + 1, 0));//dp[i][j]考虑前i个物品容量为c的背包能装下的最大价值 for (int i = 1; i <= n; i++) {//边界问题:i从1开始表示前i个,但是w和v下标都要-1 for (int j = 1; j <= c; j++) { for (int k = 0; k*v[i-1] <= j; k++) {//k=0时表示装不下的可能 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-k*v[i-1]] + k*w[i-1]); } } } return dp[n][c]; } int main() { vector<int> v = { 1,2,2,3,4 }; vector<int> w = { 1,2,3,5,7 }; cout<<backpack(v, w, 8); system("Pause"); }
还有一种写法我非常推荐的
int backpack(int n, int c, vector<int> w, vector<int> v) { vector<vector<int>> dp(n+1, vector<int>(c+1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= c; j++) { if (j - v[i-1] >= 0) { dp[i][j] = max(dp[i-1][j], dp[i][j - v[i-1]] + w[i-1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][c]; }
这里和01背包的代码区别仅仅是dp[i][j] = max(dp[i-1][j], dp[i][j - v[i-1]] + w[i-1]);
如果装的下的情况下，如果选择装，则在前i件都考虑的情况下的最大值再去装1个第件物品，来达到重复的效果
