什么样的网站空间做电影网站不卡,建网站商城有哪些公司,公司网站建设方案详细方案模板,徐州建设网站公司本文始发于个人公众号#xff1a;TechFlow#xff0c;原创不易#xff0c;求个关注今天是周三算法与数据结构专题的第12篇文章#xff0c;动态规划之零一背包问题。在之前的文章当中#xff0c;我们一起探讨了二分、贪心、排序和搜索算法#xff0c;今天我们来看另一个非…本文始发于个人公众号TechFlow原创不易求个关注今天是周三算法与数据结构专题的第12篇文章动态规划之零一背包问题。在之前的文章当中我们一起探讨了二分、贪心、排序和搜索算法今天我们来看另一个非常经典的算法——动态规划。在acm-icpc竞赛领域动态规划是一个非常大的范畴当中包含了许多变种而且很多变种难度极大。比如在各种树上和图上以及其他数据结构上做动态规划这会使得问题非常复杂。好在非竞赛选手并不需要了解到那么深入一般来说吃透背包九讲就足够笑傲各种面试了。所以周三的算法专题我们开始全新的篇章——背包系列今天和大家分享背包九讲中的第一讲也是最简单的零一背包问题。背包和零一背包没有竞赛经验的同学在看到这个标题的时候可能会一头雾水动态规划和背包有什么关系。其实没有关系我也不是陈奕迅的粉丝只是当初最经典的动态规划问题用背包做了题面还引发出了各种变种。后来在教学的时候为了方便于是沿用了前人的名称。之前我们在怪盗基德偷宝石的问题当中提到过背包问题其实很简单就是说我们当下有一个容量是V的背包和n个体积分别是v[i]价值是w[i]的五品。请问在背包容量允许的前提下我们最多能够获得多少价值的物品由于每种物品只有一个也就是物品只有拿和不拿两种状态所以这个问题被称为零一背包问题。贪心与反例这种问题我们最先想到的就是贪心法比如优先拿价值大的物品或者是性价比高的物品但是我们很容易构思出反例。举个例子比如背包的容量是10我们有3个物品体积分别是655价值是1088。这个反例可以证明两种贪心策略都不生效因为价值最大的是10它的体积是6我们一旦拿了它就没有空间再继续获取其他物品而显然拿两个5的情况是最优的。同样体积是6的物品也是性价比最高的性价比优先的贪心策略同样不生效。实际上不仅这两种贪心策略不生效所有能够想到的贪心策略都不生效。这个问题看起来简单但是并不是那么容易解决。实际上这个问题一直困扰着计算学家直到上世纪六十年代动态规划算法横空出世完美地解决了这个问题。动态规划动态规划算法的英文是dynamic programming算是很直白的翻译了。规划我们都很好理解但是动态应该怎么理解呢又怎么来动态地规划呢关于这个问题的思考直接关系到算法的本质。动态规划算法的本质是状态的记录和转移我们结合刚才的问题有没有想过为什么贪心算法不可行其实很简单因为我们没办法确定背包什么状态是完美的。虽然我们知道背包的容量是V但是我们并不知道最优的情况下我们能装多少最优的结束状态是什么。我们把空间V看成了一个状态来进行贪心贪心得到的结果是最优的但是只是贪心能达到的状态的最优解并不是全局的最优解因为背包容量的限制很有可能我们贪心策略下无法达到真正最优的状态。用刚才的例子解释一下上面这段话在贪心算法下我们会选取容量是6价值是10的物品这个物品拿取了之后背包的状态是6获取的价值是10。这个状态是贪心能够达到的最终状态对于这个状态而言它是最优解但是这个状态并不是整体最优的情况因为在贪心策略下无法达到容量10全用完的状态。理解了这个问题之后再去推导解法就顺其自然了。贪心策略可以获取一些状态最优的情况那么我们能不能记录下所有状态能够达到的最优的情况最后在这些最优的情况当中选取一个最优的它不就是整体最优解了吗动态规划正是基于上述思路展开的它解决的不是一个状态的最优解而是所有状态的最优解。状态与转移看到这里你肯定还没理解动态规划算法但是应该已经有一些大概的感觉了。这是对的有正确的感觉是正确认识的前提。我们循序渐进再来看状态这个概念。我们刚才提了这么多次究竟状态是什么呢这是一个比较抽象的概念在不同的问题当中它有着不同的含义。在背包问题当中状态指就的是背包容量的使用情况。由于背包问题中物品的体积是整数显然背包容量的可能性是有限的这点不起眼但是很重要如果状态不是整数那么虽然存在动态规划的可能但是代码实现可能比较麻烦。明白了背包的容量是状态之后我们可以进一步想明白背包的容量是会变化的。变化的原因是因为我们往里面放了东西放了东西之后背包的状态会发生变化会从一个状态转移到另一个状态。状态的转移中间伴随着我们放入东西我们放的物品并不是固定的而是有多种选择的我们决定放入A而不是BC这是一种决策决策会带来状态的转移不同的决策会带来不同的转移。比如当前有一个背包它的容量是10我们在其中已经放入了一个体积是3价值是7的物品。如果这个时候我们经过选择再放入一个体积是4价值是5的物品。那么显然背包占用的容量会变成7价值会变成12。这个过程就是一个经典的状态转移过程这也是整个动态规划算法的核心。基本的概念和思想已经介绍完了接下来就是用这些概念来解决实际问题了。最优状态我们前文说了动态规划最后会获取所有状态的最优解再从中选取全局最优的。那么它是怎么获取局部最优解的呢在回答这个问题之前我们先来思考两个问题。首先假如我们已经知道了背包体积是3时的最大价值是5这时候我们决定放入一个体积是4价值是5的物品那么背包的体积会增加到7那么这个时候获得的是体积6的最优解吗这个问题不难回答我们稍微想想就知道很有可能不是。举个最简单的例子假如我们有一个体积是7价值是20的物品。那么显然要比放这两个物品更优。虽然状态3最多能获得价值5状态7也可以由状态3转移得到但是这并不一定是最优的。也就是说最优的状态转移出去并不一定也能得到其他状态的最优值。我们把问题反过来就不一样了如果我们知道了体积6的最优解并且还知道它是由体积等于4转移得到的那么我们能不能确定体积4的状态也是对应的最优解这次的答案就变了是正确的因为如果体积4时还有更好的解法那么体积6理应也会变得更好才对这和我们的假设矛盾了。我们总结一下上面的两个结论也就是说局部最优的情况转移出去并不一定是最优的但是局部最优一定也是由其他局部最优的状态转移得到的。这句话有点像绕口令但是我觉得应该不难解释。就好比学霸去考试不一定能考第一但是考到第一的一定是学霸。局部最优就是学霸转移就是考试。局部最优转移出去并不一定是转移之后状态的最优有可能还有其他更好的转移策略但是对于某个状态最优的情况而言它一定也是从之前的某个最优状态转移得到的。并且状态的转移也是有顺序的比如在这题当中背包当中放入了物品体积只可能增加不可能减小意味着状态只能从小的转移到大的。我们捋一捋思路已经很明确了状态可以转移状态的转移有顺序局部最优一定是由其他局部最优转移得到的。由于我们并不知道当前的转移能否达到最优状态所以我们需要用一个数组或者是容器来记录所有状态历史上曾经达到过的最值。最后从所有的最值当中再选出一个最值来就是最后问题的解。到这里如果是一般的动态规划问题已经解决了但是零一背包还有一个细节需要考虑。无后效性我们先来看下整个的计算流程首先我们需要从最初状态开始这个最初的状态很好办就是背包是空的时候这时候的价值是0体积也是0这也是它的最优状态这个很好理解因为我们不能无中生有。所以我们从0开始转移状态状态转移伴随着决策在这题当中体现在选取不同的物品上。我们遍历物品作为决策再遍历能够应用这些决策的状态就拿到了所有的状态转移。最后我们用一个容器记录一下所有状态转移过程当中达到的局部最优解于是就结束了。这个过程看起来非常正常没有任何异常但实际上问题来了。我们还用刚才的题面举例背包容量是103个物品体积分别是655价值是1089。我们从0开始拿取第三个物品转移到了状态5此时的价值是9。这个时候我们继续往后遍历的话还会遍历到状态5它已经是拿取了物品3价值9的信息了。因为一个物品只能拿一次所以我们不能再用物品3转移状态5否则就违反了题意。你可能会说这个问题不难我们可以在状态当中也记录之前做过的决策嘛只要在决策的时候加一个判断就好了。表上面看是因为物品不能重复拿的限制实际上是因为我们的状态之间会有影响。也就是说我们前面做的决策很有可能影响后面的状态做决策这种状态之间的前后影响称为后效性。显然在有后效性的场景下我们是不能使用动态规划算法的并不是所有问题都可以通过加上判断解决我们需要解决后效性这个本质问题也就是说我们要想办法消除后效性。在这个问题当中这一点很容易做到。我们只需要控制一下状态和决策的遍历顺序将之前的决策与之后的决策分开使它们互不影响即可。如果我们先遍历状态再遍历每个状态可以采取的措施这样必然会造成前后影响。因为前面做了的决定后面就不能再做。但是后面并不能感知前面究竟做了什么决定。所以比较好的方法是先遍历决策再来遍历可以采取这个决策的状态。为了避免决策前后的互相影响我们采取倒序的方式遍历状态。我们举个例子假设背包容量还是10我们枚举的第一个物品体积是3价值是5。我们倒叙遍历状态7到0因为对于大于7的状态而言并不能采取这个决策总体积会超。因为对于大于7的状态而言我们不能采取这个决策总体积会超过限制对于状态7而言我们可以采取这个决策转移到状态10。我们并不知道这样转移会不会达成最优所以我们这样来记录dp[10] max(dp[10], dp[3] 5).我们接着遍历体积6可以转移到状态9。由于我们是倒序遍历所以当我们用状态7更新状态10时状态7本身并没有被这个决策更新过。即使后面我们在遍历到状态4时更新了状态7也不会影响状态10的结果。因为是倒序遍历的我们不会再用同一个策略更新到状态10了。如果是正序遍历则无法避免。同样的物品我们很有可能会出现用状态1更新状态4再用状态4更新状态7再用状态7更新状态10的情况出现。而这种情况其实对应了使用了多个同样的物品这就和题意矛盾了。举个例子假设有一个物品体积是2它的价值是5。我们遍历状态0的时候会更新状态2我们遍历到了状态2又用同样的物品更新了状态4得到了10。那么对于状态4而言它其实相当于拿了2个这个物品也就是说被同一个决策更新了两次。但是我们的物品最多只有一个显然就不对了。动态规划当中因为无法判断当前枚举的状态的来源所以不允许出现后效性如果解决不了则不能使用动态规划。这也是动态规划最基本的原则在这题当中我们是巧妙变换了决策和状态枚举的过程消除了后效性。在其他题目当中未必相同我们需要根据实际情况进行判断。如果你在做题思考的过程当中忘记了动态规划的前提就想想零一背包当中拿取物品的情况。物品只有一个只能拿一次。前面拿过了后面还能拿就违反了后效性。状态转移方程我们整理一下刚才关于状态转移的思路有以下几点我们从状态0开始状态0的最优价值是0.考虑后效性的问题确保没有后效性执行决策的时候会发生状态转移记录状态对应的最优解在这个问题当中决策就是获取物品状态就是背包容量。由于拿取物品会引起背包容量变化并且每个物品只有一个为了避免产生后效性我们需要先枚举决策再枚举状态保证每个决策只在每个状态上最多应用一次。在此过程当中需要一直记录每个状态的最优解。由于背包的容量是V我们只需要用一个容量是V的数组就足够记录所有的状态。dpdp记录的是所有的状态我们用max(dp[vi.v], dp[v] i.w)来更新dp[vi.v]状态的值由于当前的决策不一定比之前的更好所以要加上max操作保证每个状态记录下来的结果都是它最优的。当所有的状态的最优解都有了之后显然整个问题的最优解也在其中了。上面这个记录状态转移过程的式子叫做状态转移方程它也是动态规划算法的核心概念。很多时候在我们解动态规划问题的时候会在草稿纸上推演状态转移方程。如果状态转移方程能清楚地列出来距离写出代码也就不远了。代码上面的转移方程已经非常接近最后的代码了真正写出来也就只有几行而已dp 总结关于零一背包的前后推导以及当中所有的概念始末就算是介绍完了虽然我们用了这么多篇幅来介绍这个算法但是真正写成代码也就只有短短几行。单从代码行数来看动态规划可以说是实现代码最短的算法了只是虽然它代码不长但是思路并不简单尤其是当中的下标以及循环的顺序等细节希望大家不要掉以轻心。今天零一背包的问题到这里就结束了下周的算法专题我们继续背包问题来看看01背包的进阶版——完全背包和多重背包问题敬请期待。如果觉得有所收获请顺手点个关注或者转发吧你们的举手之劳对我来说很重要。
