1.不可以重复取每个物品
int beibao(vector<int> W, vector<int> V, int sum) { //使用动态规划的算法 int len = W.size(); vector<vector<int>> dp(len, vector<int>(sum+1,0)); //dp[i][j]表示的是遍历到第i个物品了，并且当前容量是j的最大价值是多少 for (int i = 1; i < len; ++i) { for (int j = 0; j <= sum; ++j) { if (j < W[i])//如果当前剩余的空间不足以装入第i个的重量，直接使用前面的 { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); } } } int maxresult = 0; for (int k = 0; k < len; ++k) { maxresult = maxresult > dp[k][sum] ? maxresult : dp[k][sum]; } return maxresult; }2.可以重复取得每个物品
int beibao_1(vector<int> W, vector<int> V, int sum) { //使用动态规划的算法 int len = W.size(); vector<int> dp(sum + 1, 0); for (int i = 1; i <= sum; ++i)//i表示的是容量为i { //dp[i] = INT_MIN; for (int j = 0; j < len; ++j) { //这里和硬币问题还不是一个问题因为硬币问题必须保证能够 //正好和想要的总数值一样的结果，而这里是可以小于总数值的 if (i >= W[j]) { //如果是第一次进来的话需要直接将结果输出，或者满足条件 if (dp[i] == 0 || (dp[i]<dp[i - W[j]] + V[j])) { //条件为选择当前的或者不选择当前的 dp[i] = dp[i - W[j]] + V[j]; } } } } return dp[sum]; }