0-1背包问题

或许在做算法题的老手手里，0-1背包问题算不上什么难事。可以说是最简单的背包问题了。
不过我之前还真没有写过0-1背包问题。
我不去仔细介绍0-1背包问题了。OI Wiki上介绍的很好：
https://oi-wiki.org/dp/knapsack/

二维动态规划

我们用来表示面对前个物品时，容量为的背包可以最多装多少价值的物品。
对于当前（第个）物品，如果我们不选择此物品，那么

如果我们挑选它，它需要占据背包的重量为，但是它产生了价值，那么

我们在选与不选中做抉择，让能产生的价值最大化，于是就有了转移方程：

如果我们用二维数组dp来表示，在程序里，转移方程就是

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);

有了关键的转移方程之后，补全两次循环，就得到了背包问题的代码。

    private static int knapsack(int[] values, int[] weights, int limit) {
        int n = values.length;
        int[][] dp = new int[n][limit + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= limit; j++) {
                if (i == 0) {
                    dp[i][j] = j >= weights[i] ? values[i] : 0;
                }
                if (i > 0 && j >= weights[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]); // 转移方程
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][limit];
    }

值得注意的是，这两次循环都是正向循环，都是从0开始逐渐递增。（后文并非如此）
二维数组、两层循环，不难得知时间复杂度，空间复杂度 。（个物品、背包容量为。）

一维动态规划

可以用滚动数组的思路，把dp这个二维数组，变成一维数组，而节约空间复杂度。
看之前的转移方程

其中这个维度上，只需要和，所以可以用滚动数组，去掉这一维度。新的转移方程

那么有的人就会写出如下代码：

    /* 错误示例！ */
    private static int knapsack2(int[] values, int[] weights, int limit) {
        int n = values.length;
        int[] dp = new int[limit + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= limit; j++) {
                //...
                if (j >= weights[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 转移方程
                }
            }
        }
        return dp[limit];
    }

这个错误的原因在于，在j的循环过程中，一边循环，一边改变了dp[j]的值。这相当于一种物品可以被购买多次。正确的做法是从大到小遍历j。

    private static int knapsack2(int[] values, int[] weights, int limit) {
        int n = values.length;
        int[] dp = new int[limit + 1];
        for (int i = 0; i < n; i++) {
            for (int j = limit; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 转移方程
            }
        }
        return dp[limit];
    }

使用一维数组，还省去了关于i、j取值的判断，整体代码整洁。
时间复杂度，空间复杂度 。空间复杂度得以优化。

完全背包问题

完全背包问题中，同一种物品可以被购买多次。实际上就是上文中的“错误”所在。只需要变更j为正序循环，就可以解决完全背包问题。

    private static int completeKnapsack(int[] values, int[] weights, int limit) {
        int n = values.length;
        int[] dp = new int[limit + 1];
        for (int i = 0; i < n; i++) {
            for (int j = weights[i]; j <= limit; j++) { // 注意逆序
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 转移方程
            }
        }
        return dp[limit];
    }