⭐️【问题导入】完全背包原题⭐️

🔐题目详情

有 $N$ 种物品和一个容量为 $C$ 的背包，每种物品都有无限件。

第 $i$ 件物品的体积是 $v[i]$ ，价值是 $w[i]$ 。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择多次的特点（在容量允许的情况下）。

示例 ：

输入: N = 2, C = 5, v = [1,2], w = [1,2]
输出: 5
解释: 选一件物品 1，再选两件物品 2，可使价值最大。

💡解题思路与代码

🍭朴素解法

我们可以直接将0-1背包的状态定义直接拿来使用：

状态定义： 不妨定义 $f[i][j]$表示从前 $i$件物品中选择，容量不超过 $j$的最大价值。

确定初始状态： 当只有一种物品选择时，由于数量是无限的，所以尽量地选就行，不要超过容量 $j$，不妨设选这一种物品的最大件数为 $k$，则有 $f[0][j]=k \times w[i],其中k\times v[i]<=j$。

状态转移方程推导： 当我们选择第 $i$件物品的时候，我们可以选择 $0,1,2...k$件，其中 $k$是最大能够选择的件数，即在不超过容量 $j$的情况下。

当我们不选择第 $i$件物品时，即 $k=0$， $f[i][j]=f[i-1][j]$。
当我们选择 $1$第 $i$件物品时，即 $k=1$， $f[i][j]=f[i-1][j - v[i]] + w[i]$。
当我们选择 $2$第 $i$件物品时，即 $k=2$， $f[i][j]=f[i-1][j - 2 * v[i]] + 2*w[i]$。
…
当我们选择 $k$第 $i$件物品时，即 $k=k$， $f[i][j]=f[i-1][j - k * v[i]]+k*w[i]$。

我们所要求的是最大的价值，所以取以上所有情况的最大值即可。

综上所述，我们的状态转移方程就出来了，不妨记当前物品的价值为：

$$f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]),k=0,1,...$$

实现代码：

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack1(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值
        int[][] f = new int[n][c + 1];
        //确定初始状态
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //状态转移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[i - 1][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[i][j] = cur;
            }
        }
        return f[n - 1][c];
    }

时间复杂度： $O(n*c*k)$， $k$的值不会大于 $c$，因为最低物品价值为 $1$，最多选择的件数不会超过 $c$。
空间复杂度： $O(n*c)$

🍭滚动数组优化空间

根据观察我们知道第 $i$行的状态仅依赖与第 $i-1$行的状态，因此我们可以使用滚动数组进行优化。

实现代码：

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack2(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值 滚动数组优化
        int[][] f = new int[2][c + 1];
        //确定初始状态
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //状态转移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            int ci = i & 1;
            int pi = (i - 1) & 1;
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[pi][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[ci][j] = cur;
            }
        }
        return f[(n - 1) & 1][c];
    }

对于时空复杂度，只是优化了空间而已，所以时间复杂度不发生改变，空间复杂度优化到 $O(c)$。
时间复杂度： $O(n*c*k)$， $k$的值不会大于 $c$，因为最低物品价值为 $1$，最多选择的件数不会超过 $c$。
空间复杂度： $O(c)$

🍭一维数组优化空间

首先我们对状态转移方程进行一个简单的推导：

$$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...,f[i-1][j-k*v[i]]+k*w[i])$$

$$f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+w[i],f[i-1][j-3*v[i]]+2*w[i]...,f[i-1][j-k*v[i]]+(k-1)*w[i])$$

其中 $k*v[i]<=j$。

通过观察上面两个状态的式子，我们发现后面一部分式子是差了一个 $w[i]$如下图：

所以我们可以进一步优化状态转移方程，即：

$$f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])$$

对于新推导出来的状态转移方程，它的状态转移仅仅只依赖与上一行同列状态与同一行元素前面的元素，所以我们可以将原来的二维数组优化为一维，由于它只依赖左边与正上方的元素，我们可以采取从小到大遍历背包容量状态来求背包中所放物品最大值。

只保留【背包容量】维度，状态转移方程为：

$$f[j]=max(f[j],f[j-v[i]]+w[i])$$

实现代码：

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack3(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值 一维数组优化
        int[] f = new int[c + 1];
        //确定初始状态f[0]=0
        //状态转移
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                //不选择物品
                int nopt = f[j];
                //选择物品
                int opt = j >= v[i] ? f[j - v[i]] + w[i] : nopt;

                f[j] = Math.max(opt, nopt);
            }
        }
        return f[c];
    }

时间复杂度： $O(n*c)$
空间复杂度： $O(c+1)$

🌱总结

以上我们介绍了【完全背包问题】的朴素解法和优化方案，其中一维优化是最复杂的，因为使用了一些数学上的推导，比较抽象，不是特别容易理解，我建议自己尝试推导一遍，这样能够更快的理解并且更深刻。
相比于0-1背包问题的优化，形式上，我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子：
0 -1 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。