01 背包问题

这个，01 背包问题，当时上课讲过呀，可惜，当时我太年轻，以为动态规划就是什么了不得的东西，导致错过了学习和巩固那些经典的动态规划的算法题的时机。好吧，其实现在也不是很晚。

这个 01 背包问题，说起来，和那个最简单的爬楼梯和斐波那契数列本质上是没有区别的。嗯。无非就是多了点参数，只要挨个弄懂，很简单的。

这里就是写了两个阐述 01 背包的方法，一个是样板代码，另一个我改了名字，更加方便我自己理解。

public class ZeroOnePack {
    /**
     * @param N   count of things
     * @param W   bag capcity
     * @param wt  weight of i-th thing
     * @param val value of i-th thing
     * @return
     */
    public int knapsack(int N, int W, int[] wt, int[] val) {
        int[][] dp = new int[N + 1][W + 1];

        for (int n = 1; n <= N; n++) {
            for (int w = 1; w <= W; w++) {
                // not suitable
                if (w - wt[n - 1] < 0) {
                    dp[n][w] = dp[n - 1][w];
                } else {
                    dp[n][w] = Math.max(dp[n - 1][w], dp[n - 1][w - wt[n - 1]] + val[n - 1]);
                }
            }
        }

        return dp[N][W];
    }

    /**
     * Just the same as the method above, and just change the names of parameters to make it easier to understand.
     *
     * @param thingsNum
     * @param bagCapcity
     * @param wtArr
     * @param valArr
     * @return
     */
    public int anotherKnapsack(int thingsNum, int bagCapcity, int[] wtArr, int[] valArr) {
        int[][] dp = new int[thingsNum + 1][bagCapcity + 1];

        for (int n = 1; n <= thingsNum; n++) {
            for (int c = 1; c <= bagCapcity; c++) {
                if (c - wtArr[n - 1] < 0) {
                    dp[n][c] = dp[n - 1][c];
                } else {
                    dp[n][c] = Math.max(dp[n - 1][c], dp[n - 1][c - wtArr[n - 1]] + valArr[n - 1]);
                }
            }
        }

        return dp[thingsNum][bagCapcity];
    }

    public static void main(String[] args) {
        var solu = new ZeroOnePack();
        int N = 3;
        int W = 4;
        var wt = new int[]{2, 1, 3};
        var val = new int[]{4, 2, 3};
        int res = solu.anotherKnapsack(N, W, wt, val);
        System.out.println(res);
    }
}

我觉得，我们唯一需要理解的事情，就是 dp[n][c] 的含义，它代表什么意思呢？

即，在容量为 c(capcity) 的情况下，从前 n 个物品中选择最优解所得到的价值，这个价值其实就是最大价值。