背包九讲完整版

h，当分配给它的费用为v时，能得到的价值就是h(v)。 这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。 一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/c*w仅当v被c整除且v/c<=n，其它情况函数值均为0。 一个物品组可以看作一个泛化物品h。对于一个0..V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。 泛化物品的和 如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0..V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数，也就是说，f是一个由泛化物品h和l决定的泛化物品。 由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v}，则称f是h与l的和，即f=h+l。这个运算的时间复杂度取决于背包的容量，是O(V^2)。 泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0..V]中的最大值。 背包问题的泛化物品 一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域（例如0..V）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。 综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。 小结 本讲可以说都是我自己的原创思想。具体来说，是我在学习函数式编程的 Scheme 语言时，用函数编程的眼光审视各类背包问题得出的理论。这一讲真的很抽象，也许在“模型的抽象程度”这一方面已经超出了NOIP的要求，所以暂且看不懂也没关系。相信随着你的OI之路逐渐延伸，有一天你会理解的。 我想说：“思考”是一个OIer最重要的品质。简单的问题，深入思考以后，也能发现更多。 首页 P09: 背包问题问法的变化 以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。 例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到。 还有，如果要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。 下面说一些变化更大的问法。 输出方案 一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。 还是以01背包为例，方程为f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。再用一个数组g[i][v]，设g[i][v]=0表示推出f[i][v]的值时是采用了方程的前一项（也即f[i][v]=f[i-1][v]），g[i][v]表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。那么输出方案的伪代码可以这样写（设最终状态为f[N][V]）： i=N v=V while(i>0) if(g[i][v]==0) print "未选第i项物品" else if(g[i][v]==1) print "选了第i项物品" v=v-c[i] 另外，采用方程的前一项或后一项也可以在输出方案的过程中根据f[i][v]的值实时地求出来，也即不须纪录g数组，将上述代码中的g[i][v]==0改成f[i][v]==f[i-1][v]，g[i][v]==1改成f[i][v]==f[i-1][v-c[i]]+w[i]也可。 输出字典序最小的最优方案 这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。 一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。 在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立，应该按照后者（即选择了物品i）来输出方案。 求方案总数 对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。 对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移方程即为 f[i][v]=sum{f[i-1][v],f[i][v-c[i]]} 初始条件f[0][0]=1。 事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。 最优方案的总数 这里的最优方案是指物品总价值最大的方案。以01背包为例。 结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[i][v]意义同前述，g[i][v]表示这个子问题的最优方案的总数，则在求f[i][v]的同时求g[i][v]的伪代码如下： for i=1..N for v=0..V f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} g[i][v]=0 if(f[i][v]==f[i-1][v]) inc(g[i][v],g[i-1][v] if(f[i][v]==f[i-1][v-c[i]]+w[i]) inc(g[i][v],g[i-1][v-c[i]]) 如果你是第一次看到这样的问题，请仔细体会上面的伪代码。 求次优解、第K优解 对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。 其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。 首先看01背包求最优解的状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。 然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果（的前K项）储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(NVK)。 为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。 另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。 小结 显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问法，只要题目难度还属于NOIP，应该也不难想出算法。触类旁通、举一反三，应该也是一个OIer应有的品质吧。 首页 附：USACO中的背包问题 USACO是USA Computing Olympiad的简称，它组织了很多面向全球的计算机竞赛活动。 USACO Trainng是一个很适合初学者的题库，我认为它的特色是题目质量高，循序渐进，还配有不错的课文和题目分析。其中关于背包问题的那篇课文 (TEXT Knapsack Problems) 也值得一看。 另外，USACO Contest是USACO常年组织的面向全球的竞赛系列，在此也推荐NOIP选手参加。 我整理了USACO Training中涉及背包问题的题目，应该可以作为不错的习题。其中标加号的是我比较推荐的，标叹号的是我认为对NOIP选手比较有挑战性的。 题目列表 l Inflate (+) （基本01背包） l Stamps (+)(!) （对初学者有一定挑战性） l Money l Nuggets l Subsets l Rockers (+) （另一类有趣的“二维”背包问题） l Milk4 (!) （很怪的背包问题问法，较难用纯DP求解） 题目简解 以下文字来自我所撰的《USACO心得》一文，该文的完整版本，包括我的程序，可在DD的USACO征程中找到。 Inflate 是加权01 背包问题，也就是说：每种物品只有一件，只可以选择放或者不放；而且每种物品有对应的权值，目标是使总权值最大或最小。它最朴素的状态转移方程是：f[k][i] = max{f[k-1][i] , f[k-1][i-v[k]]+w[k]}。f[k][i]表示前k 件物品花费代价i 可以得到的最大权值。v[k]和w[k]分别是第k 件物品的花费和权值。可以看到， f[k]的求解过程就是使用第k 件物品对f[k-1]进行更新的过程。那么事实上就不用使用二维数组，只需要定义f[i]，然后对于每件物品k，顺序地检查f[i]与f[i-v[k]]+w[k]的大小，如果后者更大，就对前者进行更新。这是背包问题中典型的优化方法。 题目stamps 中，每种物品的使用量没有直接限制，但使用物品的总量有限制。求第一个不能用这有限个物品组成的背包的大小。（可以这样等价地认为）设f[k][i] 表示前k 件物品组成大小为i 的背包， 最少需要物品的数量。则f[k][i]= min{f[k-1][i],f[k-1][i-j*s[k]]+j}，其中j 是选择使用第k 件物品的数目，这个方程运用时可以用和上面一样的方法处理成一维的。求解时先设置一个粗糙的循环上限，即最大的物品乘最多物品数。 Money 是多重背包问题。也就是每个物品可以使用无限多次。要求解的是构成一种背包的不同方案总数。基本上就是把一般的多重背包的方程中的min 改成sum 就行了。 Nuggets 的模型也是多重背包。要求求解所给的物品不能恰好放入的背包大小的最大值（可能不存在）。只需要根据“若i、j 互质，则关于x、y 的不定方程i*x+y*j=n 必有正整数解，其中n>i*j”这一定理得出一个循环的上限。 Subsets 子集和问题相当于物品大小是前N 个自然数时求大小为N*(N+1)/4 的 01 背包的方案数。 Rockers 可以利用求解背包问题的思想设计解法。我的状态转移方程如下： f[i][j][t]=max{f[i][j][t-1] , f[i-1][j][t] , f[i-1][j][t-time[i]]+1 , f[i-1][j-1][T]+(t>=time[i])}。其中 f[i][j][t]表示前i 首歌用j 张完整的盘和一张录了t 分钟的盘可以放入的最多歌数，T 是一张光盘的最大容量，t>=time[i]是一个bool 值转换成int 取值为0 或1。但我后来发现我当时设计的状态和方程效率有点低，如果换成这样：f[i][j]=(a,b)表示前i 首歌中选了j 首需要用到a 张完整的光盘以及一张录了b 分钟的光盘，会将时空复杂度都大大降低。这种将状态的值设为二维的方法值得注意。 Milk4 是这些类背包问题中难度最大的一道了。很多人无法做到将它用纯DP 方法求解，而是用迭代加深搜索枚举使用的桶，将其转换成多重背包问题再DP。由于 USACO 的数据弱，迭代加深的深度很小，这样也可以AC，但我们还是可以用纯DP 方法将它完美解决的。设f[k]为称量出k 单位牛奶需要的最少的桶数。那么可以用类似多重背包的方法对f 数组反复更新以求得最小值。然而困难在于如何输出字典序最小的方案。我们可以对每个i 记录pre_f[i]和pre_v[i]。表示得到i 单位牛奶的过程是用pre_f[i]单位牛奶加上若干个编号为pre_v[i]的桶的牛奶。这样就可以一步步求得得到i 单位牛奶的完整方案。为了使方案的字典序最小，我们在每次找到一个耗费桶数相同的方案时对已储存的方案和新方案进行比较再决定是否更新方案。为了使这种比较快捷，在使用各种大小的桶对f 数组进行更新时先大后小地进行。USACO 的官方题解正是这一思路。如果认为以上文字比较难理解可以阅读官方程序或我的程序。 首页 Copyright (c) 2007 Tianyi Cui Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation. 整理 by stntwm 多次背包 多次背包问题：给定 n 种物品和一个背包。第 i 种物品 的价值是 Wi ，其体积 为 Vi，数量是 Ki件，背包的容量为 C。可以任意选择装入背包中的物品，求装入背 包中物品的最大总价值。 方法一：可以把此物品拆分成Ki个只能用一次的物品，直接套用 0-1 背包问题的经典动规实现，但是效率太低了，需要寻找更高效的算法。此算法时间复杂度为O(C*∑(Ki)) 方法二：拆分成体积和价值分别为原来1, 2 , 4..   2^m,    Ki-2^m 倍的几个物品，用0-1背包求解。 时间复杂度为O(C*∑([log2Ki])) 方法三（本文重点）：（对单调队列没有了解的请参见原[本文结尾链接]）对于第 i 种物品来说，已知体积 v，价值 w，数量 k，那么可以按照当前枚举的体积 j 对v的余数把整个动规数组分成 v份，以下是 v=3 的情况： j             0 1 2 3 4 5 6 7 8 …… j mod v   0 1 2 0 1 2 0 1 2 …… 我们可以把每一份分开处理，假设余数为 d。 编号j         0     1        2            3           4             5         …… 对应体积 d    d+v    d+2*v     d+3*v    d+4*v      d+5*v    …… 现在看到分组以后，编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而来（因为相邻的体积正好相差 v） ，这看上去已经和区间最大值有点相似了。但是注意到由于体积不一样，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要把价值修正到同一体积的基础上。比如都退化到 d，也就是说用 F[j*v+d]- j*w来代替原来的价值进入队列。 对于物品i，伪代码如下 1. FOR d: = 0 TO v-1                     //枚举余数，分开处理 2.   清空队列 3.   FOR j: = 0 TO (C-d) div v           //j 枚举标号，对应体积为 j*v+d 4.    INSERT j , F[ j*v+d ] – j * w      //插入队列 5.    IF A[ L ] < j - k THEN L + 1 → L //如果队列的首元素已经失效 6.    B[ L ] + j * w → F[ j*v+d ]       //取队列头更新 7.   END FOR 8. END FOR 已知单调队列的效率是 O(n)，那么加上单调队列优化以后的多次背包， 效率就是 O(n*C)了。 （详细请参见原论文） ========================================================== 完整程序如下(Pascal)： var a,b,f:array[0..100000] of longint; m,s,c,n,t,i,j,l,r,d:longint; procedure insert(x,y:longint); begin while (l<=r)and(b[r]<=y) do dec(r); inc(r);a[r]:=x;b[r]:=y; end; begin readln(n,t);              //读入数据 n为物品个数 t为背包容量 for i:=1 to n do begin read(m,s,c);         //读入当前物品 m为物品体积、s为物品价值、c为物品可用次数（0表示无限制） if (c=0)or(t div m