动态规划-01背包问题

1. 最优化原理

最优化原理指的最优策略具有这样的性质：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简单来说就是一个最优策略的子策略也是必须是最优的，而所有子问题的局部最优解将导致整个问题的全局最优。如果一个问题能满足最优化原理，就称其具有最优子结构性质。

这是判断问题能否使用动态规划解决的先决条件，如果一个问题不能满足最优化原理，那么这个问题就不适合用动态规划来求解。

这样说可能比较模糊，来举个栗子吧：

如上图，求从A点到E点的最短距离，那么子问题就是求从A点到E点之间的中间点到E点的最短距离，比如这里的B点。

那么这个问题里，怎么证明最优化原理呢？

我们假设从A点到E点的最短距离为d，其最优策略的子策略假设经过B点，记该策略中B点到E点的距离为d1，A点到B点的距离为d2。我们可以使用反证法，假设存在B点到E点的最短距离d3，并且d3 < d1，那么 d3 + d2 < d1 + d2 = d，这与d是最短距离相矛盾，所以，d1是B点到E点的最短距离。

为了增加理解，这里再举一个反例：

图中有四个点，A、B、C、D，相邻两点有两条连线，代表两条通道，d1,d2,d3,d4,d5,d6代表的是道路的长度，求A到D的所有通道中，总长度除以4得到的余数最小的路径为最优路径，求一条最优路径。

这里如果还是按照上面的思路去求解，就会误入歧途了。按照之前的思路，A的最优取值应该可以由B的最优取值来确定，而B的最优取值为（3+5）mod 4 = 0。所以应该选d2和d6这两条道路，而实际上，全局最优解是d4+d5+d6或者d1+d5+d3。所以这里子问题的最优解并不是原问题的最优解，即不满足最优化原理。所以就不适合使用动态规划来求解了。

2. 无后效性

无后效性指的是某状态下决策的收益，只与状态和决策相关，与到达该状态的方式无关。某个阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。换句话说，未来与过去无关，当前状态是此前历史状态的完整总结，此前历史决策只能通过影响当前的状态来影响未来的演变。再换句话说，过去做的选择不会影响现在能做的最优选择，现在能做的最优选择只与当前的状态有关，与经过如何复杂的决策到达该状态的方式无关。

这也是用来验证问题是否可以使用动态规划来解答的重要方法。

我们再回头看看上面的最短路径问题，如果在原来的基础上加上一个限制条件：同一个格子只能通过一次。那么，这个题就不符合无后效性了，因为前一个子问题的解会对后面子问题的选择策略有影响，比如说，如果从A到B选择了一条如下图中绿色表示的路线，那么从B点出发到达E点的路线就只有一条了。也就是说从A点到B点的路径选择会影响B点到E点的路径选择。

理论部分就此打住，接下来我们实战一下。

3. 01背包问题

假设你只有一个容量有限的背包，总容量为c，有n个可待选择的物品，每个物品只有一件，它们都有各自的重量和价值，你需要从中选择合适的组合来使得你背包中的物品总价值最大。简单起见，我们来将上面的问题具体化，举一个更具体的栗子：

假设有4个物品，它们的价值(v)和重量(w)如下图：

背包总容量为10，现在要从中选择物品装入背包中，要求物品的重量不能超过背包的容量，并且最后放在背包中物品的总价值最大。

仔细想想，这里每个物品只有一个，对于每个物品而言，只有两种选择，盘它或者不盘，盘它记为1，不盘记为0，我们不能将物品进行分割，比如只拿半个是不允许的。这就是这个问题被称为0/1背包问题的原因。

所以究竟选还是不选，这是个问题。

让我们先来体验一下将珠宝装入背包的感觉，为了方便起见，用xi代表第i个珠宝的选择（xi = 1 代表选择该珠宝，0则代表不选），vi代表第i个珠宝的价值，wi代表第i个珠宝的重量。于是我们就有了这样的限制条件：

我们的初始状态是背包容量为10，背包内物品总价值为0，接下来，我们就要开始做选择了。对于1号珠宝，当前容量为10，容纳它的重量2绰绰有余，因此有两种选择，选它或者不选。我们选择一个珠宝的时候，背包的容量会减少，但是里面的物品总价值会增加。就像下面这样：

这样就分出了两种情况，我们继续进行选择，如果我们选择了珠宝1，那么对于珠宝2，当前剩余容量为8，大于珠宝2的容量3，因此也有两种选择，选或者不选。

现在，我们得到了四个可能结果，我们每做出一个选择，就会将上面的每一种可能分裂成两种可能，后续的选择也是如此，最终，我们会得到如下的一张决策图：

这里被涂上色的方框代表我们的最终待选结果，本来应该有16个待选结果，但有三个结果由于容量不足以容纳下最后一个珠宝，所以就没有继续进行裂变。

然后，我们从这些结果中，找出价值最大的那个，也就是13，这就是我们的最优选择，根据这个选择，依次找到它的所有路径，便可以知道该选哪几个珠宝，最终结果是：珠宝4，珠宝2，珠宝1。

4. 分治法

接下来，我们就来分析一下，如何将它扩展到一般情况。为了实现这个目的，我们需要将问题进行抽象并建模，然后将其划分为更小的子问题，找出递推关系式，这是分治思想中很重要的一步。

抽象问题，背包问题抽象为寻找组合（x1,x2,x3…xn，其中xi取0或1，表示第i个物品取或者不取），vi代表第i个物品的价值，wi代表第i个物品的重量，总物品数为n，背包容量为c。
建模，问题即求max(x1v1 + x2v2 + x3v3 + … + xnvn)。
约束条件，x1w1 + x2w2 + x3w3 + … + xnwn < c
定义函数KS(i,j)：代表当前背包剩余容量为j时，前i个物品最佳组合所对应的价值；

那这里的递推关系式是怎样的呢？对于第i个物品，有两种可能：

背包剩余容量不足以容纳该物品，此时背包的价值与前i-1个物品的价值是一样的，KS(i,j) = KS(i-1,j)
背包剩余容量可以装下该商品，此时需要进行判断，因为装了该商品不一定能使最终组合达到最大价值，如果不装该商品，则价值为：KS(i-1,j)，如果装了该商品，则价值为KS(i-1,j-wi) + vi，从两者中选择较大的那个，所以就得出了递推关系式：

对于这个问题的子问题，这里有必要详细说明一下。原问题是，将n件物品放入容量为c的背包，子问题则是，将前i件物品放入容量为j的背包，所得到的最优价值为KS(i,j)，如果只考虑第i件物品放还是不放，那么就可以转化为一个只涉及到前i-1个物品的问题。如果不放第i个物品，那么问题就转化为“前i-1件物品放入容量为j的背包中的最优价值组合”，对应的值为KS(i-1,j)。如果放第i个物品，那么问题就转化成了“前i-1件物品放入容量为j-wi的背包中的最优价值组合”，此时对应的值为KS(i-1,j-wi)+vi。

所以，就可以很容易的写出递归解法了：

public class Solution{
    int[] vs = {0,2,4,3,7};
    int[] ws = {0,2,3,5,5};

    @Test
    public void testKnapsack1() {
        int result = ks(4,10);
        System.out.println(result);
    }

    private int ks(int i, int c){
        int result = 0;
        if (i == 0 || c == 0){
            // 初始条件
            return result;
        } else if(ws[i] > c){
            // 装不下该珠宝
            result = ks(i-1, c);
        } else {
            // 可以装下
            // 不选择第 i 件物品
            int tmp1 = ks(i-1, c);
            // 选择第 i 件物品
            int tmp2 = ks(i-1, c-ws[i]) + vs[i];
            result = Math.max(tmp1, tmp2);
        }
        return result;
    }
}

这里为了方便处理，将数组ws和vs都增加了一个补位数0，防止数组越界，输出结果：

这样，我们就轻松加愉快的解决了这个问题。

5. 动态规划解法

5.1 验证可行性

既然开头已经说了两个验证问题是否可以使用动态规划求解的方法，那么为何不试一试呢？

先来看看最优化原理。同样，我们使用反证法：

假设(x1，x2，…，xn)是01背包问题的最优解，则有(x2，x3，…，xn)是其子问题的最优解，假设(y2，y3，…，yn)是上述问题的子问题最优解，则有(v2y2+v3y3+…+vnyn)+v1x1 > (v2x2+v3x3+…+vnxn)+v1x1。说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理。

至于无后效性，其实比较好理解。对于任意一个阶段，只要背包剩余容量和可选物品是一样的，那么我们能做出的现阶段的最优选择必定是一样的，是不受之前选择了什么物品所影响的。即满足无后效性。

5.2 自上而下记忆法

自上而下的解法与分治法的区别就是增加了一个数组用来存储计算的中间结果来减少重复计算。这里，我们只需要多定义一个二维数组。

表格中，每一个格子都代表着一个子问题，我们最终的问题是求最右下角的格子的值，也就是i=4,j=10时的值。这里，我们的初始条件便是i=0或者j=0时对应的ks值为0，这很好理解，如果可选物品为0，或者剩余容量为0，那么最大价值自然也是0。代码如下：


public class Solution {
    int[] vs = {0,2,4,3,7};
    int[] ws = {0,2,3,5,5};
    Integer[][] results = new Integer[5][11];

    @Test
    public void testKnapsack2() {
        int result = ks2(4,10);
        System.out.println(result);
    }

    private int ks2(int i, int c){
        int result;
        // 如果该结果已经被计算，那么直接返回
        if (results[i][c] != null) return results[i][c];
        if (i == 0 || c == 0){
            // 初始条件
            result = 0;
        } else if(ws[i] > c){
            // 装不下该珠宝
            result = ks2(i-1, c);
        } else {
            // 可以装下
            int tmp1 = ks2(i-1, c);
            int tmp2 = ks2(i-1, c-ws[i]) + vs[i];
            result = Math.max(tmp1, tmp2);
        }
        results[i][c] = result;
        return result;
    }
}

可以看到，其实只比分治多了三行代码。

5.3 自下而上填表法

接下来，我们用自下而上的方法来解一下这道题，思路很简单，就是不断的填表，还是使用上面的表格，我们开始一行行填表。

当i=1时，即只有珠宝1可供选择，那么如果容量足够的话，最大价值自然就是珠宝1的价值了。

当i=2时，有两个物品可供选择，此时应用上面的递推关系式进行判断即可。这里以i=2,j=3为例进行分析：

剩下的格子使用相同的方法进行填充即可：

这样，我们就得到了最后的结果：13。根据结果，我们可以反向找出各个物品的选择，寻找的方法很简单，就是从i=4,j=10开始寻找，如果ks(i-1,j)=ks(i,j)，说明第i个物品没有被选中，从ks(i-1,j)继续寻找。否则，表示第i个物品已被选中，则从ks(i-1,j-wi)开始寻找。

转化成代码：


public class Solution{
    int[] vs = {0,2,4,3,7};
    int[] ws = {0,2,3,5,5};
    int[][] results = new int[5][11];
    
    @Test
    public void testKnapsack3() {
        int result = ks3(4,10);
        System.out.println(result);
    }

   /**
    * ks(i,c) = max{ks(i-1, c), ks(i-1, c-ws[i]) + vs[i]}(条件：c>=ws[i])
    * ks(i,c) = ks(i-1,c)(条件：c<ws[i])
    */
    private int ks3(int i, int j){
        // 开始填表
        for (int m = 1; m <= i; m++){
            for (int n = 1; n <= j; n++){
                if (n < ws[m]){
                    // 装不进去
                    results[m][n] = results[m-1][n];
                } else {
                    // 容量足够
                    results[m][n] = Math.max(results[m - 1][n], results[m - 1][n - ws[m]] + vs[m]);
                }
            }
        }
        return results[i][j];
    }
}

嗯，完美解决。时间复杂度即填表耗时O(n * c)，这里用了一个二维数组来存储子问题的解，所以空间复杂度为O(n * c);

5.4 空间优化过程

自下而上填表发这种解法，我们还能再对它的空间复杂度进行优化。再回头看下之前的递推关系式：

可以发现，每次求解 KS(i,j)只与KS(i-1,m) {m:1...j} 有关。也就是说，如果我们知道了K(i-1,1...j)就肯定能求出KS(i,j)，为了更直观的理解，再画一张图：

下一层只需要根据上一层的结果即可推出答案，举个栗子，看i=3，j=5时，在求这个子问题的最优解时，根据上述推导公式，KS(3,5) = max{KS(2,5),KS(2,0) + 3} = max{6,3} = 6;如果我们得到了i=2时所有子问题的解，那么就很容易求出i=3时所有子问题的解。

因此，我们可以将求解空间进行优化，将二维数组压缩成一维数组，此时，装填转移方程变为：

1	KS(j) = max{KS(j), KS(j - wi) + vi}

这里KS(j - wi)就相当于原来的KS(i-1, j - wi)。需要注意的是，由于KS(j)是由它前面的KS(m){m:1..j}推导出来的，所以在第二轮循环扫描的时候应该由后往前进行计算，因为如果由前往后推导的话，前一次循环保存下来的值可能会被修改，从而造成错误。

这么说也许还是不太清楚，回头看上面的图，我们从i=3推算i=4的子问题的解时，此时一维数组中存放的是{0,0,2,4,4,6,6,6,7,7,9}，这是i=3时所有子问题的解，如果我们从前往后推算i=4时的解，比如，我们计算KS(0) = 0，KS(1) = KS(1) = 0 (因为j=1时，装不下第三个珠宝，第三个珠宝的重量为5)，KS(2) = 2,KS(3) = 4,KS(4) = 4, KS(5) = max{KS(5), KS(5-5) + 7} = 7,....,KS(10) = max{KS(10),KS(10 - 5) + 7} = 14。在这里计算KS(8)的时候，我们就把原来KS(5)的内容修改掉了，这样，我们后续计算就无法找到这个位置的原值，也就是上一轮循环中计算出来的值了，所以在遍历的时候，需要从后往前进行倒序遍历。

public class Solution{
    int[] vs = {0,2,4,3,7};
    int[] ws = {0,2,3,5,5};
    int[] newResults = new int[11];

    @Test
    public void test() {
        int result = ksp(4,10);
        System.out.println(result);
    }
    
    /**
     * 空间优化版
     * ks(c) = max{ks‘(c), ks‘(c-ws[i]) + vs[i]}(条件：c>=ws[i])
     * ks(c) = ks‘(c)(条件：c<ws[i])
     * ks(c) 等同于 ks(i,c)，ks‘(c-ws[i]) 等同于 ks(i-1, c-ws[i])，通过逆向遍历复用前一次结果来实现该等同效果
     */
    private int ksp(int i, int c){
        // 开始填表
        for (int m = 0; m < vs.length; m++){
            // n >= w 即剩余空间大于重量时，才装填
            for (int n = c; n >= ws[m]; n--){
                newResults[n] = Math.max(newResults[n] , newResults[n - ws[m]] + vs[m]);
            }
            // 可以在这里输出中间结果
            System.out.println(JSON.toJSONString(newResults));
        }
        return newResults[newResults.length - 1];
    }
}

输出如下：

[0,0,0,0,0,0,0,0,0,0,0]
[0,0,2,2,2,2,2,2,2,2,2]
[0,0,2,4,4,6,6,6,6,6,6]
[0,0,2,4,4,6,6,6,7,7,9]
[0,0,2,4,4,7,7,9,11,11,13]
13

这样，我们就顺利将空间复杂度从O(n*c)优化到了O(c)。当然，空间优化的代价是，我们只能知道最终的结果，但无法再回溯中间的选择，也就是无法根据最终结果来找到我们要选的物品组合。

5.5 关于初始值

01背包问题一般有两种不同的问法，一种是“恰好装满背包”的最优解，要求背包必须装满，那么在初始化的时候，除了KS(0)为0，其他的KS(j)都应该设置为负无穷大，这样就可以保证最终得到的KS(c)是恰好装满背包的最优解。另一种问法不要求装满，而是只希望最终得到的价值尽可能大，那么初始化的时候，应该将KS(0...c)全部设置为0。

为什么呢？因为初始化的数组，实际上是在没有任何物品可以放入背包的情况下的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么都不装且价值为0的情况下被“恰好装满”，其他容量的背包均没有合法的解，因此属于未定义的状态，应该设置为负无穷大。如果背包不需要被装满，那么任何容量的背包都有合法解，那就是“什么都不装”。这个解的价值为0，所以初始状态的值都是0。

6. 总结

回过头再看看上面的分析，会发现动态规划里最关键的问题其实是寻找原问题的子问题，并写出递推表达式，只要完成了这一步，代码部分都是水到渠成的事情了。

那么问题来了，怎样把问题拆分成子问题呢？

emmm，这个问题有点超纲了，说实话，我也没有掌握到诀窍，还是得具体情况具体分析，但是很多经典的问题都有其经典的套路，其它问题都可以归结到这些问题上面来，可以看做是它们的变种和延伸，把这些经典的问题吃透的话，自然能举一反三。比如采药问题，本质上就是01背包问题，而硬币问题，本质上就是我们之后要介绍的完全背包问题。

01背包问题可以用自上而下的递归记忆法求解，也可以用自下而上的填表法求解，而后者可以将二维数组的解空间优化成一维数组的解空间，从而实现空间复杂度的优化。

对于01背包问题的两种不同问法，实际上的区别便是初始值设置不一样，解题思路是一样的。

关于01背包问题，介绍到这里就已经全部结束了，希望能对大家有所帮助。

个人认为，算法不在于刷多少个，而在于归纳总结，就跟做数学题一样，总有一些范式和套路，不管形式如何变化，其本质是一样的，万变不离其宗，说的就是这么回事。