背包问题-动态规划

题目：给定两个数组w和v， 两个数组长度相等， w[i]表示第i件商品的重量，v[i]表示第i件商品的价值。再给定一个整数bag， 要求你挑选商品的重量加起来一定不能超过bag， 返回满足这个条件下， 你能获得的最大价值。

思路一：递归版本

递归函数代表从第index位置开始满足条件时的最大价值，比如：process1(w,v,bag,index,cost)代表从index位置开始，返回满足条件的最大价值，cost代表目前商品的重量。

public static int process(int[] w, int[] v, int bag) {
        return process1(w,v,bag,0,0);
}

/**
*  递归函数代表从第index位置开始满足条件时的最大价值
*/
private static int process1(int[] w, int[] v, int bag, int index, int cost ) {
        if(cost > bag) return Integer.MIN_VALUE;
        if (index == w.length) return 0;
        return Math.max(process1(w, v, bag, index+1, cost), v[index] + process1(w, v, bag, index+1, cost+w[index]));
}

思路2：动态规划版本
根据递归函数可知，解空间只取决于index、cost两个变量，故dp数组是一个二维数组，根据basecase可以知道dp二维数组第index=w.length行的值均为0，根据递推式二维数组的二维表每一行依赖于后一行的数值，因此二维表可以从倒序填好，从而得到整个dp数组的值，二维表画个图更直观。（懒，省略。。）

    private static int process2(int[] w, int[] v, int bag) {
        int n = w.length;
        int[][] dp = new int[n+1][bag+1];
        for (int i=n-1;i>=0;i--) {
            for (int j=bag;j>=0;j--) {
                dp[i][j] = dp[i+1][j];
                if(w[i] + j<=bag) dp[i][j] = Math.max(dp[i][j], v[i]+dp[i+1][w[i]+j]);
            }
        }
        return dp[0][0];
    }