- 完全背包问题 -

完全背包

问题定义：

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

注意： 完全背包问题 和 01背包问题唯一不同的地方就是，每种物品有无限件

题解

1. 定义dp数组dp[i][j]:
   i表示 从0-i 序号的物品选择
   j表示此时背包的容纳重量
   数组的值表示该条件下的背包里物品的最大价值

2. 递推表达式：
   依旧分为两种情况，对于dp[i][j]:

   • 不放物品i: 背包容量为j， 那么背包不放物品i的最大价值为dp[i-1][j]
   • 放物品i: 背包空出物品i后，还剩j - weight[i]的容量，此时与 01背包问题不同，由于物品可以重复放入，所以对于剩余j - weight[i]容量仍然可以放入物品i， 因此此时最大价值为dp[i][j-weight[i]] + value[i]。不同于01背包的dp[i-1][j-weight[i]] - value[i]

   因此递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

3. 初始化
   因为递归表达式同时与i行 和i - 1行相关，因此，需要初始化dp[0][...]以及dp[...][0]。

   对于dp[0][...]:
   当j < weight[0]时: 容量不够放，因此dp[0][j] = 0
   当j >= weight[0]时:dp[0][j]如果能放下weight[0]的话，就一直装，每一种物品有无限个

   对于dp[...][0]: 因为背包容量为0，所以初始值为0

   初始化代码：

   // 初始化 因为dp数组默认为0，所以对于 dp[...][0] 不用刻意 去初始化for(intj=weight[0];j<=bagWeight;j++){dp[0][j]=dp[0][j-weight[0]]+value[0];}

4. 遍历顺序
   先遍历物品和先遍历背包都可以，便于理解先遍历物品 即从左到右 从上到下

问题变形