背包问题九讲和源程序（答案）(3)

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选手比较有挑战性的。 题目列表

? Inflate (+) （基本01背包）

? Stamps (+)(!) （对初学者有一定挑战性） ? Money ? Nuggets ? Subsets

? Rockers (+) （另一类有趣的“二维”背包问题）

? 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 的官方题解正是这一思路。如果认为以上文字比较难理解可以阅读官方程序或我的程序。

1、01背包：

program ZeroOnePack;//01背包 const

maxv=20000; maxn=3000; var

f:array[0..maxv]of longint; n,v:longint;

procedure main; var

i,j,w,c,max:longint; begin

readln(n,v);

for i:=0 to v do f:=0; for i:=1 to n do begin

readln(c,w);// 输入一个物品费用为c，价值为W for j:=v downto 0 do if c+j<=v then

if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程 end; max:=f[0];

for i:=1 to v do if f>max then max:=f; writeln(max); end;

begin

assign(input,'Pack.in'); reset(input);

assign(output,'Pack.out'); rewrite(output); main;

close(input); close(output); end.

-------------------------------------------- 2、完全背包

program CompletePack;//完全背包 const

maxv=20000; maxn=3000; var

f:array[0..maxv]of longint; n,v:longint; procedure main; var

i,j,w,c,max:longint; begin

readln(n,v);

for i:=0 to v do f:=0; for i:=1 to n do begin

readln(c,w);// 输入一个物品费用为c，价值为W for j:=0 to v do//故意重复使用 if c+j<=v then

if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程 end; max:=f[0];

for i:=1 to v do if f>max then max:=f; writeln(max); end; begin

assign(input,'Pack.in'); reset(input);

assign(output,'Pack.out'); rewrite(output); main;

close(input); close(output); end.

------------ 3、多重背包

program MultiplePack;//多重背包 const

maxv=20000; maxn=3000; var

f:array[0..maxv]of longint;

c,w,n:array[1..maxn]of longint; num,v:longint;

procedure makeobject; var

i,k,num2:longint; begin

num2:=num;

for i:=1 to num do begin

if c*n>v then n:=v div c; k:=2;

while k*2-1<=n do//2进制思想 begin

inc(num2);

c[num2]:=c*k;w[num2]:=w*k; k:=k*2; end; k:=n-k+1;

if k>0 then //补足n begin

inc(num2);

c[num2]:=c*k;w[num2]:=w*k; end; end; num:=num2; end;

procedure main; var

i,j,max:longint; begin

readln(num,v);

for i:=1 to num do read(c,w,n); makeobject;//制造倍数物品 for i:=0 to v do f:=0; for i:=1 to num do begin

for j:=v downto 0 do if c+j<=v then

if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程 end; max:=f[0];

for i:=1 to v do if f>max then max:=f; writeln(max);

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库背包问题九讲和源程序（答案）(3)在线全文阅读。