算法细节系列（9）：动态规划之01背包

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434850

动态规划

本文参考《挑战程序设计竞赛》，通过01背包问题，引出动态规划，争取把它的原理阐述清楚，话不多说，直接开始吧。

问题描述

Problem:

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装 入背包中物品的总价值最大?

Example:

输入：undefined n = 5 (w,v) = {(77,92),(22,22),(29,87),(50,46),(99,90)} C = 100 输出： 133

先说说一种最暴力的方法吧，对于每一件物品，我们可以选择（选or不选），那么n件物品就会有2n2^n种选法，我们就从这2n2^n中选法中，挑出符合背包容量c，但价值最大的那个组合就好了。代码如下：

public static int solve(int[] w, int[] v, int c){
        return select(0, w, v, c);
    }


    //start 从第一件物品开始
    private static int select(int start,int[] w, int[] v, int c){
        int value = 0;

        //终止条件，没有物品可选时，价值为0
        if (start == w.length){
            value = 0;
        }
        //如果当前物品的容量已经超过背包，则不用选择
        else if (c < w[start]){
            value = select(start+1, w, v, c);
        }
        //符合容量的情况下，有两种状态（选or不选），取其中最大
        else{
            value = Math.max(select(start + 1, w, v, c),select(start+1, w, v, c-w[start])+v[start]);
        }

        return value;
    }

上述代码运用了递归的手段来进行破解，相比以前的递归式，有很多不一样的地方，如递归分了状态，如value = Math.max(select(start + 1, w, v, c),select(start+1, w, v, c-w[start])+v[start]);，这种递归式对状态是有选择性的，也是真正时间复杂度为O(2n)O(2^n)的罪魁祸首，当前状态为了得到全局信息，需要递归遍历后续的所有状态才能进行决策，这种策略何等的落后。

曾困惑我的一点在于它的准确性，我始终不理解为什么递归最后能引向正确答案。这里简单解释下，因为递归的本质在于数学归纳，我们假设的始终是前一个状态的准确性，如果能找到状态间唯一的性质来构建当前状态，那么它就能随着状态的累加逐步得到正确解。这就好比多米诺骨牌，一个骨牌可以代表一个状态，而骨牌与骨牌之间的距离是状态变动的条件，假设骨牌1能被推倒，且能够击打到第2个骨牌，而状态变动条件始终不变（骨牌间的距离始终不变），那么就能从第1个骨牌推倒第n个骨牌。它是一种数学证明公理，所以形象理解数学归纳法即可。

就拿这个问题来说，我们是假设知道如何选择下一状态的物品，由下一状态来得到当前状态。所以理解代码准确性的关键点在于，假设我们拿到了下一状态的两个value（背包容量分别为c和c-wnow），如果当前容量不够容下此物品，那么就直接返回value，而当前容量足够容下此物件，那么一定选择下一状态中较大的那个value。

关注这句话value = Math.max(select(start + 1, w, v, c),select(start+1, w, v, c-w[start])+v[start]);,以后看到这样的递归形式一定要敏感，它是我们可以优化的重点考虑对象。刚才说了，每次都有两个状态的递归，那么一次递归2个分支，2个分支产生的递归有4个分支，而终止条件是start == w.length，这表明递归的深度为n，计算一下，它有2n2^n种情况。而在这么多种情况下，难道就没有重复的吗！！！（感性的认识）

动态规划思想来源

重复子问题对我来说有点难以分析，这要看具体的问题场景，但在分析重复子问题相对复杂的情况下，我们不管三七二十一，可以在它的搜索路径上记录状态，而为了记录状态，我们需要【标识】出到达每一个状态！

重点来了，递归是无状态的，或者说对于计算机而言，它无法区分每个状态。那么如果我们能在递归过程中用某些唯一变量来标识递归状态，那么当遇到相同状态时，我们可以直接在函数顶返回！

所以，现在有了一个可行的优化手段，在上述代码中，找寻到变量能区分递归状态即可。

static int[][] dp = null;
    public static int solve(int[] w, int[] v, int c){
        dp = new int[w.length+1][c+1];
        return select(0, w, v, c);
    }


    private static int select(int start,int[] w, int[] v, int c){

        if (dp[start][c] > 0){
            return dp[start][c];
        }

        int value = 0;
        if (start == w.length){
            value = 0;
        }

        else if (c < w[start]){
            value = select(start+1, w, v, c);
        }

        else{
            value = Math.max(select(start + 1, w, v, c),select(start+1, w, v, c-w[start])+v[start]);
        }

        return dp[start][c] = value;
    }

很明显，如果单纯的只考虑状态数，算一算dp数组的大小就可以了，因为现在每个dp都表示一种状态，所以时间复杂度为O(nc)O(nc)。这也就说明了另外一件事情，重复子问题的状态范围只能在0-n,0-c，而如果范围没有约束，dp可能就无助于问题求解。

动态规划正解

刚才是从递归的角度，为了解决状态的记录来推得动态规划，建立dp数组是为了记录中间变量，也就是我们经常听到的一个概念，记忆化搜索。

但从上述问题的优化过程，它能给我们其它的思路，原本O(2n)O(2^n)的复杂度，降低到了O(nw)O(nw)，说明该问题在暴力搜索时，已经证明了状态的重复性。所以，我们可以从数学归纳法的角度反过来求解该问题，刚才的递推式如下：

dpn=0

dpn = 0

dpi={dpi+1,j<wimax(dpi+1,dpi+1j−wi]+vi)

dpi = \begin{cases} dpi+1, j \lt wi\ max(dpi+1,dpi+1j-wi]+vi) \end{cases}

关键问题就在于找状态转移和初始状态，所以有了这玩意，我们就可以直接写迭代代码了，正确性在前文已经阐述过了，当然你也可以自己脑海中过一遍，01背包问题还是容易理解的。我在初学时，总喜欢跟着代码想把状态转移搞清楚，这没有必要，我们应该从问题本身来理解状态转移递推式。一个技巧就是，假设第n-1阶段的所有状态你已经知道了，而此时你去考虑需要加些什么条件能够构建第n阶段的解，基本上如果你有思路了，问题也就被你解决了。

public static int dpSolve(int[] w, int[] v, int c){
        int[][] dp = new int[w.length + 1][c + 1];

        for (int j = 0; j <= c; j++){
            dp[w.length][j] = 0;
        }

        for (int i = w.length-1; i>= 0; i--){
            for (int j = 0; j <= c; j++){
                if (w[i] > j){
                    dp[i][j] = dp[i+1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
                }
            }
        }

        return dp[0][c];
    }

为了代码的可读性，我还是做了初始化操作，其实数组本身在new出来后为0，所以可以省略这部分代码。

这是反向选择，正向选择就不可以么？同样的，代码如下：

public static int dpSolve2(int[] w, int[] v, int c) {
        int[][] dp = new int[w.length + 1][c + 1];

        for (int i = 0; i < w.length; i++) {
            for (int j = 0; j <= c; j++) {
                if (w[i] > j) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
                }
            }
        }

        return dp[w.length][c];
    }

这里采用的思路和以上所有的解决方案是一样的，只是遍历方向性变了。背包中的物件拿取顺序不影响答案，容易理解。总结一下，从问题的初始态一步步求解的方法就叫动态规划。解决问题时既可以按照如上方法从记忆化搜索出发推导出递推式，也可以直接得出递推式。

另一种搜索思路

在看另一种搜索思路时，我们再来回顾下之前的递归解法，注意如下判断语句：

int value = 0;
if (start == w.length){
    value = 0;
}

这有什么特别的么，终止条件value为0的，这就意味着当搜索到最底层时，在往上构建解的时候要对value值进行累加，所以起初value随着递归层数的增加没有变化，而在返回时，value的解开始发生变化了。如下：

value = Math.max(select(start + 1, w, v, c),select(start+1, w, v, c-w[start])+v[start]);

好了，我们直接看一种value在往下搜索过程中不断更新的情况。代码如下：

private static int select2(int start, int[] w, int[] v, int c, int sum){

        int value = 0;
        if (start == w.length){
            value = sum;
        }

        else if (c < w[start]){
            value = select2(start + 1, w, v, c, sum);
        }

        else{
            value = Math.max(select2(start + 1, w, v, c, sum), select2(start + 1, w, v, c-w[start], sum + v[start]));
        }

        return value;
    }

发现一个明显的区别了么，终止条件返回的是sum，而sum是在递归过程中不断更新的，当递归返回时，value选择较大的sum作为当前层的结果，直到第一层。

此时，如果你和第一种递归方式一样采取记忆化措施，会发现答案是错的。这是为什么？容易想象，当你一路记录sum值后，sum的变化跟路径相关，这就意味着，到达每个状态sum是唯一的，如果你此时对sum做记忆化，那么竞选的结果就和路径无关了，很显然与这种求解方法矛盾了。所以，如果对记忆化搜索不熟练的话，容易犯以上错误。

总结

简单总结一下我所理解的动态规划。就拿01背包问题来说，它的解法可以非常暴力，直接用递归，对每种情况进行遍历，但我们看到。我们代码并不像刚开始人为求解的思路一样，而是在选择和不选择之间做了一些判断。但它的时间复杂度却没有发生质的变化，为O(2n)O(2^n)，但我们发现，这种递归结构会存在重复子问题，可以参考《挑战程序设计竞赛》P52页的递归调用图。

既然存在重复子问题，我们需要在递归时把这些状态给区分出来，所以我们有了dp数组，也就是第二种记忆化方案，而这才是我认为动态规划的雏形或者叫精髓，用唯一标识表示状态（唯一标识变量需要我们去寻找）。

既然有了递归，而递归本质上是数学归纳法的逆向过程，而且很大程度上记忆化搜索依赖递归的解法，如果对递归不熟悉容易出现记忆化搜索失灵，与其这样，我们不如由递归式写出递推式，建立初始态，和状态转移递推式，以迭代的方式一步步求解正确解，这种过程就叫动态规划。

最后推荐一则知乎关于动态规划的回答【什么是动态规划？动态规划的意义是什么？】，在这些回答中，关于动态规划的理解更加深刻与全面，待补足一些知识后，我再补充。

上述所有代码可以fork下Github上leetcode项目，不定期更新leetcode刷题进度。链接地址：https://github.com/demonSong/leetcode