问题描述
有\(N\)件物品和一个容量是\(V\)的背包，每件物品都有无限件可用。
第\(i\)种物品的体积是\(v_i\)，价值是\(w_i\)。求解将哪些物品装入背包，可使这些物品总体积不超过背包容量，且总价值最大。
解题思路
内层嵌套循环
01背包问题每样物品只能使用一件，而针对完全背包问题，我们只需要在内层有关体积的循环中，再添加一层循环，枚举一共使用了多少件物品\(i\)即可。
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
for (k = 1; k * v[i] <= j; k++) {
dp[j] = max(dp[j], dp[j - k * v[i] + k * w[i]);
}
}
}
更改遍历方向
在01背包问题中，我们内层关于体积的循环，是从大到小的，这是为了保证在比较max(dp[j], dp[j - v[i]] + w[i])时，使用的是上一次i循环的数值；
而在完全背包问题中，内层关于体积的循环，修改成从小到大即可，此时dp = max(dp[j], dp[j - v[i]] + w[i])中，dp[j - v[i]] + w[i]使用的就是本次i循环中的数值，而i循环中,dp[j - v[i]] = max(dp[j - v[i]], dp[(j - v[i]) - v[i]] + w[i]),依次往前递推，总能找到那个最大值dp[j - k * v[i]] + k * w[i]。
事实上，内层的体积循环中，遍历方向由大到小就是保证每个物品只使用一次，由小到大则是可以使用无限次。
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}