1、背包问题（2）2010 年 3 月 11 日晚培训内容：1、砝码称重的背包解法。2、Subset Sums 集合的背包解法。3、数字游戏。4、滚动数组的应用。砝码称重的背包解法【问题分析】 1 1 1 2 2 3 3 3 把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 wi, wi 1,2,3,5,10,20 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。这样一改就是经典的 0/1 背包问题的简化版了。把 a1 个砝码看成 0/1 背包中的第 1 个物品，重量与价值均为 a1*1。把 a2 个砝码看成 0/1 背包中的第 2 个物品，重量与价值均为 a2
2、*2。只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。http:/ fmcz;const w:array1.6of 1.20=(1,2,3,5,10,20);maxll=1001;vari,j:longint;a,b:array1.10of longint;f:array1.1001of longint;beginfor i:=1 to 6 dobeginread(ai);bi:=ai*wi;end;readln;for i:=1 to 6 dobeginfor j:=maxll downto bi dobeginif fj-bi+bifj then fj:=fj-bi+b
3、i;体积与价值相同end;end;writeln(fmaxll);maxll 能达到多少就有多少种重量end.砝码称重的测试数据如下：41 1 1 0 0 0 0 Total=342 2 2 0 0 0 0 Total=643 1 0 3 0 0 0 Total=744 3 4 0 5 0 0 Total=3645 2 2 2 2 2 2 Total=8246 0 3 2 7 4 5 Total=18547 0 6 3 4 2 1 Total=7948 1 2 3 4 5 6 Total=20448 6 5 4 3 2 1 Total=83410 10 10 10 10 1 1 Total=1
4、40Subset Sums 集合背包解法http:/ Sums集合对于从 1 到 N 的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 N=3，对于1 ，2，3能划分成两个子集合，他们每个的所有数字和是相等的： 3 and 1,2 这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果 N=7，有四种方法能划分集合1 ，2，3，4，5，6，7，每一种分发的子集合各数字和是相等的: 1,6,7 and 2,3,4,5 注 1+6+7=2+3+4+5 2,5,7 and 1,3,4,6 3,4,7 and 1,2,5,6 1,2,4,
5、7 and 3,5,6 给出 N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出 0。程序不能预存结果直接输出。PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行，且只有一个整数 NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出 0。SAMPLE OUTPUT (file subset.out)4 当 1 到 n 的总和为奇数时，一定没有一种方案，可以直接输出 0，否则把总和 div 2当作背包的容量，用 1 到 n 个数去做 0/1 背包，把每一种情况加起来，状态方程：fj
6、=fj+fj-i ，由于 n 个数都使用了两次，所以情况总数也就是答案的 2 倍，所以输出时div 2 就可以了。不知道为什么的请看下面：如 n=3 时,s=3;集合有1,2和3,3和1,2这样就重复了,所以 div 2。 fj集合的是由j-i和i组合的.fj-i有几种情况，那 j-i 和 i 的组合就有几种情况了，这是加法原理。program subset;var n,i,j:longint;s:int64;st:array0.390of int64;beginassign(input,subset.in);reset(input);assign(output,subset.out);rew
7、rite(output);while not eof dobeginread(n);s:=(n+1)*n shr 1;if s and 1=1 then writeln(0)elsebegins:=s shr 1;for i:=1 to n dofor j:=s downto i dofj:=fj+fj-i;writeln(fs shr 1);end;end;close(input);close(output);end.var f:array0.100000of int64;i,n,m,j:longint;beginassign(input,subset.in);reset(input);as
8、sign(output,subset.out);rewrite(output);readln(n);close(input);m:=(1+n)*n div 2;if m mod 2=1 then begin writeln(0); close(output); halt; end;m:=m div 2;f0:=1;for i:=1 to n dobeginfor j:=m-i downto 0 dofi+j:=fi+j+fj; fm=fm+fm-1 fm-1=fm-1+fm-2end;writeln(fm div 2);close(output);end.动态规划一般解决两类问题，一类是最优化
9、问题,就是问你最大价值最小数什么的，另一类是方案总数问题。http:/ DP 之中，在 DP 过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在 01 背包问题中，从理解角度讲我们应开 DPij的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得 DPi,只需使用 DPi - 1的信息，DPi - k,k1 都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个 DPij需要由 DPi - 1 k,DPi - 2k决定，i0
10、then if f1-c,j-ti+pifc,j then fc,j:=f1-c,j-ti+pi; （mod 2）end; end; writeln(pall-fc,k); /close(input); close(output); end.1、P34：数字游戏要求：能读懂该程序；能回答该题后面提出的一个问题：把两阶段的程序段合并成一段。思考：如果要将 ai、 ai+1、a i+2、a j-1、 aj 分成 p 部分，怎样分？将 ai、a i+1、a k 、 ak+1、a k+2aj 分成 p-1 部分 分成第 p 部分比如：把 1、2、3、4、5、6 分成 2 部分，1 2 3 4 5 6如
11、果 ai、a i+1、a k 、 ak+1、a k+2aj 不在一条直线上，而是在圆周上，怎么划分呢？m-1 部分由 i. j 组成。第 m 部分由 1.i-1 和 j+1.n 组成。1in1jnikj-1m -1 部分第 m 部分12i4j6kfor i:=1 to n do 计算一部分内的数和对 10 的模的所有可能情况 for j:=i+1 to n do begin gi，j:= (gi ，j-1+gj，j) mod 10; fmax1i，j:=gi，j;fmin1i， j:=gi，j; end;for本题的计算过程分两个阶段 第一个阶段：将圆周上的 n 个数排成一个序列，计算 ai、
12、ai+1、aj 划分成 m-1 个部分的最大值 fmax1i，j和最小值 fmin1i，j； 第二个阶段：将序列首尾相接。枚举第 m 部分的所有可能情况，在 fmax1 和 fmin1的基础上，计算圆周上的 n 个数划分成 m 个部分的最大值 max 和最小值 min。 由于是一个圈,所以要从 1-n 中的每个点打断进行 DP,最后统计最大最小值思考：能否将两个阶段合并，用一个状态转移方程来解决呢？请修改程序。for p:=2 to m-1 do 阶段：递推计算划分 2 部分m-1 部分的结果值 begin fillchar(fmax，sizeof(fmax)，0); 划分 p 部分的状态转移
13、方程初始化 fillchar(fmin，sizeof(fmin)，$FF); for i:=1 to n do 状态：枚举被划分为 p 部分的数字区间 for j:=i to n do for k:=i to j-1 do 决策：a i.ak 被划分成 p-1 部分begin if fmax1i，k*gk+1，jfmaxi，j then 计算将 ai、ai+1、aj 划分成 p 个部分的状态转移方程 fmaxi，j:=fmax1i，k*gk+1 ，j; if(fmin1i，k=0)and(fmin1i，k*gk+1，j1) or (jmax thenmax:=(g1，i-1+gj+1，n) m
14、od 10*fmax1i，j; if(fmin1i，j=0) and (g1，i-1+gj+1 ，n) mod 10*fmin1i ，jfj,k then fj,k:=value*fl,k-1;if value*gl,k-1gn,m then min:=gn,m;end;writeln(min);234 -1writeln(max);end.var a,b:array0.100of longint; f1,f2:array0.10,0.52of longint; num:array0.51,0.51of longint; n,m,i,t,max1,min1,j,k:longint; funct
15、ion max(x,y:longint):longint; begin if xy then max:=x else max:=y; end; function min(x,y:longint):longint; begin if xy then min:=y else min:=x; end; begin readln(n,m); for i:=1 to n do readln(ai); a0:=an; max1:=-maxlongint; min1:=maxlongint; for t:=1 to n do begin fillchar(num,sizeof(num),0); fillch
16、ar(b,sizeof(b),0); fillchar(f1,sizeof(f1),0); fillchar(f2,sizeof(f2),0); for i:=t to t+n-1 do bi-t+1:=ai mod n; for i:=1 to n do for j:=i to n do numi,j:=(numi,j-1+(bj+10000000) mod 10) mod 10; for i:=1 to n do begin f11,i:=num1,i; f21,i:=num1,i; end; for i:=2 to m do for j:=i to n do begin f2i,j:=m
17、axlongint; for k:=i-1 to j-1 do begin f1i,j:=max(f1i,j,f1i-1,k*numk+1,j); f2i,j:=min(f2i,j,f2i-1,k*numk+1,j); end; end; if f1m,nmax1 then max1:=f1m,n; if f2m,nmin1 then min1:=f2m,n; end; writeln(min1); writeln(max1); end.for k:=1 to m-1 do for i:=1 to n do for l:=0 to n-1 do begin j:=i+l; f2i,j,k mod 2:=1000000; for t:=i+1 to j do begin f1i,j,k mod 2:=max(f1i,j,k,f1i,t-1,(k-1) mod 2*sumt,j); f2i,j,k mod 2:=min(f2i,j,k,f2i,t-1,(k-1) mod 2*sumt,j); end; 滚动数组做的，到底是 PJ 的题啊，M 可以到 200，滚动数组就发威了，一般的数组 MEL all in all,the numbers are too small
