暴力递归到动态规划 03 （背包问题）

1. 题目

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

2. 暴力递归

如果剩余空间<0，则返回-1
如果选完最后一个，再选就直接返回0
对于一个物品，可以选，可以不选
如果不选，curIndex+1,这个物品直接跳过
如果选，判断返回来的值是不是 -1 ，如果不是，则添加新价值

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

    /** * 从左往右 01背包 * * @param weight 物品重量数组 * @param value 物品价值数组 * @param bagFreeSpace 背包剩余空间 * @param curIndex * @return */
    private int getValue(int[] weight, int[] value, int bagFreeSpace, int curIndex) {
    
        //如果剩余空间<0
        if (bagFreeSpace < 0) {
    
            return -1;
        }
        if (curIndex == value.length) {
    
            //如果选完最后一个 value[value.length - 1]
            return 0;
        }
        //如果当前物品不选，则直接选下一个
        int unSelect = getValue(weight, value, bagFreeSpace, curIndex + 1);
        //如果当前物品可以选
        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数组，横向为选择的物品，纵向为当前背包容量
由递归的返回过程可知，当选完所有物品，即 curIndex == n , 则dp[ n ] [ curIndex] = 0
由下往上递归 （第 n - 1 行开始，第 n 行全部为0），从左往右循环
如果不选，为dp[i+1][j]
如果选，value[i] + dp[i + 1][j - weight[i]]
在连两者中选最大值

 public int getMaxValue2(int[] weight, int[] value, int bagSize) {
    
        int n = weight.length;
        //横向为背包剩余空间
        //纵向为当前选择的物品
        int[][] dp = new int[n + 1][bagSize + 1];
        //由暴力递归可知，当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++) {
    
                //如果当前物品不选，则直接选下一个
                int unSelect =dp[i+1][j];
                //如果当前物品可以选
                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));
    }