动态规划—01背包问题

01背包问题属于经典的动态规划问题，场景描述如下：

形象描述：贼，夜入豪宅，可偷之物甚多，而负重能力有限，偷哪些才更加不枉此行？

进一步抽象的话，就是：
给定个物品，每种物品都有自己的重量和价值，在限定的总重量/总容量内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高

顶级抽象描述就是数学语言了，数学语言描述如下：
条件：
1: 个数对
2: 正整数
求解0-1规划问题：

0-1背包问题子结构：选择一个给定物品，则需要 比较 选择 的形成的子问题的最优解 与 不选择 的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

0-1背包问题递归过程：设有n个物品，背包的重量为，为最优解。即只需要一个判断三条件的公式就能求出最优解：

有了这个判断三条件的公式，代码实现起来就比较轻松了，Java实现源码如下：

public class CB {
    public static void main(String[] args) {
        int totalWeight = 10;                    //物品个数，背包容量
        Bean[] data = new Bean[]{new Bean(0, 0),
                new Bean(2, 6), new Bean(2, 3), new Bean(6, 5), new Bean(5, 4), new Bean(4, 6)};
        System.out.println(getMaxValue(data, totalWeight));
    }

    public static int getMaxValue(Bean[] data, int totalWeight) {
        int n = data.length;
        int[][] table = new int[n][totalWeight + 1];
        for (int i = 1; i < n; i++) { //物品
            for (int w = 1; w <= totalWeight; w++) {  //背包大小
                if (data[i].weight > w) {
                    //当前物品i的重量比背包容量j大，装不下，肯定就是不装
                    table[i][w] = table[i - 1][w];
                } else { //装得下，Max{装物品i， 不装物品i}
                    table[i][w] = Math.max(table[i - 1][w], table[i - 1][w - data[i].weight] + data[i].value);
                }
            }
        }
        for (int f = 0; f < table.length; f++) {
            System.out.println(Arrays.toString(table[f]));
        }
        return table[n - 1][totalWeight];
    }

    static class Bean {
        int weight = 0;
        int value = 0;

        Bean(int w, int v) {
            weight = w;
            value = v;
        }

        @Override
        public String toString() {
            return weight + "  " + value;
        }
    }
}

我们初始化五个数对，总重量，算法的最终输出如下：