背包问题九讲-dd_engi
本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分,这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结,名为《解动态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。
背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题,我也将它放在我的写作计划的第一部分。
读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长,思路也偶有跳跃的地方,后面更有需要大量思考才能理解的比较抽象的内容。更重要的是:不大量思考,绝对不可能学好动态规划这一信息学奥赛中最精致的部分。
你现在看到的是本文的1.0正式版。我会长期维护这份文本,把大家的意见和建议融入其中,也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。但目前本文还没有一个固定的发布页面,想了解本文是否有更新版本发布,可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子,每次比较重大的版本更新都会在这里发贴公布。
如果有任何意见和建议,特别是文章的错误和不足,或者希望为文章添加新的材料,可以通过 这个网页 联系我(dd_engi)。
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即fi表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
fi=max{fi-1,fi-1]+w[i]}。</p>
<p>这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f i-1]再加上通过放入第i件物品获得的价值w[i]。</p>
<p>注意fi有意义当且仅当存在一个前i件物品的子集,其费用总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是fN的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项fi,这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以,由你自己来体会了。</p>
<h3 id="优化空间复杂度">优化空间复杂度</h3><p>以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。</p>
<p>先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组fi的所有值。那么,如果只用一个数组f [0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态fi呢?fi是由fi-1和f[i-1] [v-c[i]]两个子问题递推而来,能否保证在推fi时(也即在第i次主循环中推f[v]时)能够得到fi-1和fi-1]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态fi -1]的值。伪代码如下:
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};</p>
<p>其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程fi=max{fi-1,fi- 1]},因为现在的f[v-c[i]]就相当于原来的fi-1]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了fi由fi]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。</p>
<p>事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。{!背过}</p>
<p>我们看一下原来的方程fi=max{fi-1,fi-1]+w[i]}。不一定从1开始,那样会浪费 。 </p>
<p>过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}</p>
<p>注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。</p>
<p>有了这个过程以后,01背包问题的伪代码就可以这样写:
for i=1..N
ZeroOnePack(c[i],w[i]);</p>
<h3 id="初始化的细节问题">初始化的细节问题</h3><p>我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。</p>
<p>如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。</p>
<p>如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。</p>
<p>为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。</p>
<p>这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。</p>
<h3 id="总结">总结</h3><p>01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。</p>
......
<h2 id="P02-完全背包问题">P02: 完全背包问题</h2><h3 id="题目-1">题目</h3><p>有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。</p>
<h3 id="基本思路-1">基本思路</h3><p>这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令fi表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:fi=max{fi-1]+kw[i]|0<=kc[i]<= v}。这跟01背包问题一样有O(NV)个状态需要求解,但求解每个状态的时间则不是常数了,求解状态fi的时间是O(v/c[i]),总的复杂度是超过O(VN)的。</p>
<p>将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。</p>
<h3 id="一个简单有效的优化">一个简单有效的优化</h3><p>完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。</p>
<h3 id="转化为01背包问题求解">转化为01背包问题求解</h3><p>既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c [i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。</p>
<p>更高效的转化方法是:把第i种物品拆成费用为c[i]2^k、价值为w[i]2^k的若干件物品,其中k满足c[i]*2^k<V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c[i]))件物品,是一个很大的改进。</p>
<p>但我们有更优的O(VN)的算法。</p>
<p>###O(VN)的算法
这个算法使用一维数组,先看伪代码:
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};</p>
<p>你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态fi是由状态fi-1]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果fi-1]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果fi],所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。</p>
<p>这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等价地变形成这种形式:
fi=max{fi-1,fi]+w[i]}</p>
<p>将这个方程用一维数组实现,便得到了上面的伪代码。</p>
<p>最后抽象出处理一件完全背包类物品的过程伪代码,以后会用到:
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}</p>
<h3 id="总结-1">总结</h3><p>完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。</p>
<h2 id="P03-多重背包问题">P03: 多重背包问题</h2><h3 id="题目-2">题目</h3><p>有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。</p>
<h3 id="基本算法">基本算法</h3><p>这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取 n[i]件。令fi表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:
fi=max{fi-1]+ kw[i]|0<=k<=n[i]}</p>
<p>复杂度是O(V*∑n[i])。</p>
<h3 id="转化为01背包问题">转化为01背包问题</h3><p>另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i]件01背包中的物品,则得到了物品数为∑n[i]的01背包问题,直接求解,复杂度仍然是O(V*∑n[i])。</p>
<p>但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想,我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外,取超过n[i]件的策略必不能出现。</p>
<p>方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。</p>
<p>分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示,这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出,并不难,希望你自己思考尝试一下。</p>
<p>这样就将第i种物品分成了O(log n[i])种物品,将原问题转化为了复杂度为O(V*∑log n[i])的01背包问题,是很大的改进。</p>
<p> 下面给出O(log amount)时间处理一件多重背包中物品的过程,其中amount表示物品的数量:
procedure MultiplePack(cost,weight,amount)
if costamount>=V
CompletePack(cost,weight)
return
integer k=1
while k<num
ZeroOnePack(kcost,kweight)
amount=amount-k
k=k2
ZeroOnePack(amountcost,amountweight)</p>
<p> 希望你仔细体会这个伪代码,如果不太理解的话,不妨翻译成程序代码以后,单步执行几次,或者头脑加纸笔模拟一下,就会慢慢理解了。</p>
<h3 id="O-VN-的算法">O(VN)的算法</h3><p>多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程,但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围,故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。</p>
<h3 id="小结">小结</h3><p>这里我们看到了将一个算法的复杂度由O(V∑n[i])改进到O(V∑log n[i])的过程,还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法,自己证明一下它的正确性,并用尽量简洁的程序来实现。</p>
<h2 id="P04-混合三种背包问题">P04: 混合三种背包问题</h2><h3 id="问题">问题</h3><p>如果将P01、P02、P03混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢?</p>
<h3 id="01背包与完全背包的混合">01背包与完全背包的混合</h3><p>考虑到在P01和P02中最后给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类物品可以取无限次,那么只需在对每个物品应用转移方程时,根据物品的类别选用顺序或逆序的循环即可,复杂度是O(VN)。伪代码如下:</p>
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
<h3 id="再加上多重背包">再加上多重背包</h3><p>如果再加上有的物品最多可以取有限次,那么原则上也可以给出O(VN)的解法:遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话,用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。</p>
<p>当然,更清晰的写法是调用我们前面给出的三个相关过程。</p>
<p>混血儿的优势for 所有的组k
for 所有的i属于组k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}
<p> 注意这里的三层循环的顺序,甚至在本文的beta版中我自己都写错了。“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。</p>
<p>另外,显然可以对每组中的物品应用P02中“一个简单有效的优化”。</p>
<h3 id="小结-3">小结</h3><p>分组的背包问题将彼此互斥的若干物品称为一个组,这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题(例如P07),由分组的背包问题进一步可定义“泛化物品”的概念,十分有利于解题。</p>
<h2 id="P07-有依赖的背包问题">P07: 有依赖的背包问题</h2><h3 id="简化的问题">简化的问题</h3><p>这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。</p>
<h3 id="算法-1">算法</h3><p>这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。</p>
<p>按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择一个附件,选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。(事实上,设有n个附件,则策略有2^n+1个,为指数级。)</p>
<p>考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略),所以一个主件和它的附件集合实际上对应于P06中的一个物品组,每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法,因为物品组中的物品还是像原问题的策略一样多。</p>
<p>再考虑P06中的一句话:可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们,对于一个物品组中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,我们可以对主件i的“附件集合”先进行一次01背包,得到费用依次为0..V-c[i]所有这些值时相应的最大价值f’[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组,其中费用为c[i]+k的物品的价值为f’[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的,通过一次01背包后,将主件i转化为 V-c[i]+1个物品的物品组,就可以直接应用P06的算法解决问题了。</p>
<h3 id="较一般的问题">较一般的问题</h3><p>更一般的问题是:依赖关系以图论中“森林”的形式给出(森林即多叉树的集合),也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。</p>
<p>解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是,由于附件可能还有附件,就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合,则它必定要被先转化为物品组,然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。</p>
<p>事实上,这是一种树形DP,其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后,你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。</p>
<h3 id="小结-4">小结</h3><p>NOIP2006的那道背包问题我做得很失败,写了上百行的代码,却一分未得。后来我通过思考发现通过引入“物品组”和“依赖”的概念可以加深对这题的理解,还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系:物品不能既作主件又作附件,每个主件最多有两个附件,可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组,这便揭示了问题的某种本质。</p>
<p>我想说:失败不是什么丢人的事情,从失败中全无收获才是。</p>
<h2 id="P08-泛化物品">P08: 泛化物品</h2><h3 id="定义">定义</h3><p>考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。</p>
<p>更严格的定义之。在背包容量为V的背包问题中,泛化物品是一个定义域为0..V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。</p>
<p>这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组h[0..V],给它费用v,可得到价值h[V]。</p>
<p>将所有的背包普遍化:</p>
<p>1.一个费用为c价值为w的物品,如果它是01背包中的物品,那么把它看成泛化物品,它就是除了h(c)=w其它函数值都为0的一个函数。i=N
v=V
while(i>0)
if(gi==0)
print "未选第i项物品"
else if(gi==1)
print "选了第i项物品"
v=v-c[i]
<p>另外,采用方程的前一项或后一项也可以在输出方案的过程中根据fi的值实时地求出来,也即不须纪录g数组,将上述代码中的g[i] [v]==0改成fi==fi-1,gi==1改成fi==fi-1]+w[i]也可。</p>
<h3 id="输出字典序最小的最优方案">输出字典序最小的最优方案</h3><p>这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。</p>
<p>一般而言,求一个字典序最小的最优方案,只需要在转移时注意策略。首先,子问题的定义要略改一些。我们注意到,如果存在一个选了物品1的最优方案,那么答案一定包含物品1,原问题转化为一个背包容量为v-c[1],物品为2..N的子问题。反之,如果答案不包含物品1,则转化成背包容量仍为V,物品为2..N的子问题。不管答案怎样,子问题的物品都是以i..N而非前所述的1..i的形式来定义的,所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下,以下按物品已被逆序排列来叙述。</p>
<p>在这种情况下,可以按照前面经典的状态转移方程来求值,只是输出方案的时候要注意:从N到1输入时,如果fi==f[i-v]及fi==fi-1]+w[i]同时成立,应该按照后者(即选择了物品i)来输出方案。{取I与不取I相比,取的话一定在字典前}</p>
<h3 id="求方案总数">求方案总数</h3><p>对于一个给定了背包容量、物品费用、物品间相互关系(分组、依赖等)的背包问题,除了再给定每个物品的价值后求可得到的最大价值外,还可以得到装满背包或将背包装至某一指定容量的方案总数。</p>
<p>对于这类改变问法的问题,一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品,转移方程即为:for i=1..N
for v=0..V
fi=max{fi-1,fi-1]+w[i]}
gi=0
if(fi==fi-1)
inc(gi,gi-1
if(fi==fi-1]+w[i])
inc(gi,gi-1])
<p>如果你是第一次看到这样的问题,请仔细体会上面的伪代码。</p>
<h3 id="求次优解、第K优解">求次优解、第K优解</h3><p>对于求次优解、第K优解类的问题,如果相应的最优解问题能写出状态转移方程、用动态规划解决,那么求次优解往往可以相同的复杂度解决,第K优解则比求最优解的复杂度上多一个系数K。</p>
<p>其基本思想是将每个状态都表示成有序队列,将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。</p>
<p>首先看01背包求最优解的状态转移方程:fi=max{fi-1,fi-1]+w[i]}。如果要求第K优解,那么状态fi就应该是一个大小为K的数组fi[1..K]。其中fi[k]表示前i个物品、背包大小为v时,第k优解的值。“fi是一个大小为K的数组”这一句,熟悉C语言的同学可能比较好理解,或者也可以简单地理解为在原来的方程中加了一维。显然fi[1..K]这K个数是由大到小排列的,所以我们把它认为是一个有序队列。</p>
<p>然后原方程就可以解释为:fi这个有序队列是由fi-1和fi-1]+w[i]这两个有序队列合并得到的。有序队列fi-1即fi-1[1..K],fi-1]+w[i]则理解为在fi-1][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果(的前K项)储存到fi[1..K]中的复杂度是O(K)。最后的答案是fN[K]。总的复杂度是O(NVK)。</p>
<p>为什么这个方法正确呢?实际上,一个正确的状态转移方程的求解过程遍历了所有可用的策略,也就覆盖了问题的所有方案。只不过由于是求最优解,所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组,并在这个数组中有序的保存该状态可取到的前K个最优值。那么,对于任两个状态的max运算等价于两个由大到小的有序队列的合并。</p>
<p>另外还要注意题目对于“第K优解”的定义,将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。</p>
<h3 id="小结-6">小结</h3><p>显然,这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域(例如数论、图论)结合起来的问题,在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程,遇到其它的变形问法,只要题目难度还属于NOIP,应该也不难想出算法。</p>
<p>触类旁通、举一反三,应该也是一个OIer应有的品质吧。</p>
<h2 id="P11-背包问题的搜索解法">P11: 背包问题的搜索解法</h2><p>《背包问题九讲》的本意是将背包问题作为动态规划问题中的一类进行讲解。但鉴于的确有一些背包问题只能用搜索来解,所以这里也对用搜索解背包问题做简单介绍。大部分以01背包为例,其它的应该可以触类旁通。</p>
<h3 id="简单的深搜">简单的深搜</h3><p>对于01背包问题,简单的深搜的复杂度是O(2^N)。就是枚举出所有2^N种将物品放入背包的方案,然后找最优解。基本框架如下: