动态规划算法(01背包问题)

一. 动态规划算法介绍：

动态规划算法和分治算法类似，也是将待求解问题分成若干个小问题一步步求解，不同的是，每一个小问题求解过程依赖于上一个小问题的解。动态规划问题可以通过填表法来得到解，最经典的应用就是背包问题。

二. 背包问题：

1. 背包问题介绍：

背包问题，就是有一个能装重量为X的背包，现有重量W和价值V各不相同的几件物品，在不超过背包容量X的情况下，如何使得背包内物品的总价值V最大。如果可以装相同的物品，称为完全背包问题，不可以装相同的物品，称为01背包问题。

2. 填表法推导过程：

假如现有一个背包容量为4，现有3件物品，其价值和体积如下表：

物品	重量W	价值V
A	1	15
B	4	30
C	3	20

在物品不能相同的情况下，如何装才能使总价值最大呢？显然是把A和C都装进背包，可以获得总价值为35，这种情况是最优的，那么是如何推导出来的呢？

我们可以把这个问题分成一个个的小问题来解决，现在的背包能装的重量是4，那我们就看看背包容量为1、2、3、4的时候，装东西能产生的最大价值分别是多少。这里要注意两点：

• 分配容量的规则为最小重量的整数倍，这里物品最小重量是1，所以分别看背包容量为1、2、3、4时装东西的最大价值；如果最小重量是2，那么就看背包容量为2、4的时候能装的最大价值。

• 后一个问题的解依赖于前一个问题的解。

现在用填表法来解决这个背包问题：

物品\背包容量	0	1	2	3	4
无
A
B
C

首先说明一下这个表，0,1,2,3,4表示的是背包容量，A，B，C表示的是物品，“无”表示的是没有物品的时候。空出来的格子就填写当前能够得到的最大价值。显然第二行和第二列都是0，第二行表示不装东西的时候，那么不管背包容量是多少，不装东西价值都是0；第一列表示背包容量为0的时候，啥都装不了，所以价值也是0。

物品\背包容量	0	1	2	3	4
无	0	0	0	0	0
A	0
B	0
C	0

那么接下来就看第三行，即只装物品A的时候，能够得到的最大价值。因为规定了不能放入重复的物品，所以即使容量足够的情况下也只能放入一件物品A，所以在容量不够装A之前，价值是0，能够装A之后，价值就是A的价值，即15。

物品\背包容量	0	1	2	3	4
无	0	0	0	0	0
A	0	15	15	15	15
B	0
C	0

接下来再看第四行，第四行的时候，不是只能装B，之前说的那句话，“后一个问题的解依赖于前一个问题的解”，即第四行的时候，是要考虑装A的情况，即要依赖第三行。

• 第四行第三列：容量为1，没得选，因为B的重量是4，只能装A，所以这里填15(没得选的情况，就直接把上一行该列的值复制下来即可)；

• 第四行第四列：容量为2，也没得选，复制上一行该列的值；

• 第四行第五列：容量为3，还是没得选，复制上一行该列的值；

• 第四行第六列：容量为4，可以选择装B，也可以不装B。怎么判断装不装呢？看B的价值是否大于该列上一行的值，B的价值是30，而该列上一行的值是15,30更大，所以我们选择装B，这里填入30，而且装了B之后就没有剩余容量了。

物品\背包容量	0	1	2	3	4
无	0	0	0	0	0
A	0	15	15	15	15
B	0	15	15	15	30
C	0

来看最后一行：

• 第五行第三列：容量为1，没得选，因为C的重量是3，装不下，所以直接复制上一行该列的值，即15；

• 第五行第四列：容量为2，也没得选，复制上一行该列的值；

• 第五行第五列：容量为3，可以选择装C，也可以选择不装复制上一行该列的值，但是C的价值是20，大于15，所以这里填20，而且装了C之后没有剩余容量了；

• 第五行第六列：容量为4，可以选择装C，也可以不装C。不装的话，就直接复制上一行该列的值，是30；如果装C，C消耗的容量是3，价值是20，还剩余1个容量，那么就去容量为1的那一列，找一个最大值，是15，因为20 + 15 = 35 > 30，所以这里填入35。

物品\背包容量	0	1	2	3	4
无	0	0	0	0	0
A	0	15	15	15	15
B	0	15	15	15	30
C	0	15	15	20	35

通过上面这个推导过程可以发现，A对应的这一行就只考虑物品A的情况，B这一行不仅要考虑B，还要考虑A，C这一行就要考虑A和B。当有A、B、C三种物品且背包容量为4时，能够获得的最大价值就是C这一行，4对应的这一列的值，即35。

3. 总结公式：

我们把上面的第二行第二列开始的部分看成是一个二维数组，如下：

0	0	0	0	0
0	15	15	15	15
0	15	15	15	30
0	15	15	20	35

所以二维数组可以定义成：

int[][] tv = new int[4][5]

tv[i][j]就表示前i个物品，装入容量为j的背包时，能够获得的最大价值。
4怎么来的？总共有3件物品，加上没有物品的情况，就是4；5怎么来的？背包容量被我们拆成了1、2、3、4，再加上容量为0的情况，就是5。

我们再定义一个数组用来保存物品的重量：

int[] w = {1,4,3}; // 物品的重量

还需要定义一个数组来保存物品的价值：

int[] v = {15,30,20}; // 物品的价值

(1). tv[i][0] = 0，表示第一行都是0；tv[0][j] = 0，表示第一列都是0；

(2). w[i]表示的是第i件物品的重量，v[i]表示的是第i件物品的价值；j是列的索引，第0列表示背包容量为0时，第1列表示背包容量为1时，所以j表示的是当前背包的容量。

(3). 当w[i] > j时，那么就让tv[i][j] = tv[i-1][j]。也就是说，第i件物品的重量大于当前背包的容量时，那么久直接将上一行该列的那个值复制过来。

(4). 当w[i] <= j时，那么就让tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}。条件就是第i件物品的重量小于等于背包容量时，此时有两种情况，一个是装，一个是不装，怎么判断装不装呢，那就判断装能获得的总价值更大还是不装能获得的总价值更大。

• 如果不装第i件物品，能获得的最大价值那就和上一行该列的值一样，即tv[i-1][j]；

• 如果装第i件物品，能够获得的最大价值就是第i件物品的价值加上装了第i件物品后剩余容量能够获得的价值。v[i]是第i件物品的价值，怎么理解tv[i-1][j-w[i]]？首先看j-w[i]，意思就是当前背包容量减去第i件物品的重量，那也就是当前背包容量下如果装第i件物品后剩余的容量，所以tv[i-1][j-w[i]]的意思就是，去上一行找背包容量为j-w[i]时的那个值，也就是当前背包装了第i件物品后剩余容量能够获得的最大价值；v[i] + tv[i-1][j-w[i]]就是如果装第i件物品能够获得的最大价值。

• 经过上面的分析，tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}就很好理解了，当背包容量为j时，装前i件物品能够获得的最大价值就是在装与不装两种情况中取最大值。

3. 代码实现：

public class BagProblem {
    
    public static void main(String[] args) {
        int[] w = {1,4,3}; // 物品的重量
        int[] v = {15,30,20}; // 物品的价值
        int m = 4; // 背包的容量
        System.out.println(maxValue(w, v, m));
    }
    
    public static int maxValue(int[] w, int[] v, int m) {
        int n = w.length; // 物品个数
        int[][] tv = new int[n+1][m+1];
        for(int i=0; i<v.length; i++) {
            tv[i][0] = 0; // 第一列全部设置为0
        }
        for(int i=0; i<tv[0].length; i++) {
            tv[0][i] = 0; // 第一行全部设置为0
        }
        for(int i=1; i<tv.length; i++) {
            for(int j=1; j<tv[0].length; j++) {
                if (w[i-1] > j) { // 循环中i从1开始，所以要减1
                    tv[i][j] = tv[i-1][j];
                } else {
                    // 循环中i从1开始，所以w和v中的i要减1
                    tv[i][j] = Math.max(tv[i-1][j], v[i-1] + tv[i-1][j-w[i-1]]);
                }
            }
        }
        return tv[n][m];
    }

}