完全背包
区别:
每种物品都是可以无线多个
代码:
1 // 多背包问题 2 // 有N个物品,他们的体积和重量如下,但是这些物品有无限个 3 // 需要发挥背包的最大容量,来让价值最大 4 // 5 // dp[n]: 当容量为N的时候,背包的价值最大是多少 6 // dp[n]: 7 // dp[n] 8 // dp[n-weight[i]]+values[i] 9 // 10 // dp[0] = 0 11 // 12 int test_CompletePack(vector<int>& weight, vector<int>& value, int& bagWeight) 13 { 14 vector<int> dp(bagWeight + 1, 0); 15 16 for (int i = 0; i < weight.size(); i++) 17 { 18 for (int j = weight[i]; j <= bagWeight; j++) 19 { 20 dp[j] = max(dp[j], value[i] + dp[j - weight[i]]); 21 } 22 } 23 24 return dp[bagWeight]; 25 }