前置知识：01背包

概念：完全背包

相对于01背包，完全背包是物品数量无限的背包，也就是说，一个物品，我们想要拿多少拿多少（只要背包装得下）。

这就很不一样了，我们具体来看看 $\tt DP$ 怎么推。

思路：构建 $\tt DP$

想要让数量无限，我们可以同样设置和 $01$ 背包一样的状态，也就是：

1 2	dp[i][j]; // 表示：前 i 个物品里选择出体积为 j 的最大价值

那么问题就是，如何在这个的基础上，做到每一个物品选好多次。

题外话：一个粗劣的算法

所谓数量无限其实只是你背包装不下，也就是说，从某种意义上来讲，我们可以在加一层循环，枚举某一个物品买了几次的01背包。
1
2
3
4
for(int i = 1; i <= n; i++) // 枚举物品
    for(int j = 0; j <= v; j++) // 枚举体积
        for(int k = 0; k * c[i] <= j; k++) // 三重循环 枚举每种取用件数*c[i]不大于当前总体积j
            dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i] * k] + w[i] * k);

我们知道，再01背包中，当 $i - 1$ 递推到 $i$ 时，我们认为他购买了可以使当前问题最优的物品（没买也属于），也就是说，01背包始终是从旧的状态推到新的状态。那么按照这个说法，我们只需要让完全背包每次递推都从新的状态上面递推，我们就可以得到完全背包的代码。

代码：基础的完全背包

按照上面的思路，就可以轻松写出如下代码

for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= V; j++) {
        dp[i][j] = dp[i - 1][j];
        if(j - a[i] >= 0){
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i]);
        }
    }
}

优化：好一点的完全背包

按照01背包压维的方法，这就是最后压缩空间后的代码了

for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= V; j++) {
        if(j - a[i] >= 0){
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
}