Brute force recursion to dynamic programming 03 (knapsack problem)

1. 题目

有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和？

2. 暴力递归

如果剩余空间<0,则返回-1
If choose the last one,Choose directly back to0
对于一个物品,可以选,可以不选
如果不选,curIndex+1,This item just skip
如果选,Figure out whether returns to the value of the -1 ,如果不是,The add new value

   public int getMaxValue(int[] weight, int[] value, int bagSize) {
    
        return getValue(weight, value, bagSize, 0);
    }

    /** * 从左往右 01背包 * * @param weight 物品重量数组 * @param value 物品价值数组 * @param bagFreeSpace Pack the remaining space * @param curIndex * @return */
    private int getValue(int[] weight, int[] value, int bagFreeSpace, int curIndex) {
    
        //如果剩余空间<0
        if (bagFreeSpace < 0) {
    
            return -1;
        }
        if (curIndex == value.length) {
    
            //If choose the last one value[value.length - 1]
            return 0;
        }
        //If the current items don't choose,Directly under the selected one
        int unSelect = getValue(weight, value, bagFreeSpace, curIndex + 1);
        //If the current item can choose
        int select = 0;
        int next = getValue(weight, value, bagFreeSpace - weight[curIndex], curIndex + 1);
        if (next != -1) {
    
            select = value[curIndex] + next;
        }
        //选择最大价值
        return Math.max(unSelect, select);
    }

2. 动态规划

dp数组,Lateral to select items,Vertical to the current volume
By a recursive process of return the,Elected all items,即 curIndex == n , 则dp[ n ] [ curIndex] = 0
Recursive from down to up （第 n - 1 行开始,第 n 行全部为0）,From left to right circulation
如果不选,为dp[i+1][j]
如果选,value[i] + dp[i + 1][j - weight[i]]
In even the maximum

 public int getMaxValue2(int[] weight, int[] value, int bagSize) {
    
        int n = weight.length;
        //Lateral to pack the remaining space
        //Longitudinal to the currently selected item
        int[][] dp = new int[n + 1][bagSize + 1];
        //Recursive knowable by violence,当curIndex==n , 则为0
        // Java 默认为0
        for (int i = 0; i <=bagSize; i++) {
    
            dp[n][i] = 0;
        }
        //物品
        for (int i = n-1; i >= 0; i--) {
    
            for (int j = 0; j <= bagSize; j++) {
    
                //If the current items don't choose,Directly under the selected one
                int unSelect =dp[i+1][j];
                //If the current item can choose
                int select = 0;
                if (j >= weight[i]) {
    
                    select = value[i] + dp[i + 1][j - weight[i]];
                }
                dp[i][j] = Math.max(unSelect, select);
            }
        }
        return dp[0][bagSize];
    }
    public static void main(String[] args) {
    
        int[] weights = {
    3, 2, 4, 7};
        int[] values = {
    5, 6, 3, 19};
        int bag = 11;
        System.out.println(new Package().getMaxValue(weights, values, bag));
        System.out.println(new Package().getMaxValue2(weights, values, bag));
    }