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);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32