背包问题培训学案.doc

背包问题（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。只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。/2009/05/27/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%925%e2%80%94%e2%80%94%e7%ae%97%e6%b3%95%e4%b8%8e%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84/#more-610program 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+bi;体积与价值相同end;end;writeln(fmaxll);maxll能达到多少就有多少种重量end.砝码称重的测试数据如下：411 1 0 0 0 0Total=3422 2 0 0 0 0Total=6431 0 3 0 0 0Total=7443 4 0 5 0 0Total=36452 2 2 2 2 2Total=82460 3 2 7 4 5Total=185470 6 3 4 2 1Total=79481 2 3 4 5 6Total=204486 5 4 3 2 1Total=8341010 10 10 10 1 1Total=140Subset Sums 集合背包解法/sifx_xu/blog/item/e4ea06eadfb53cd5d539c986.htmlSubset 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,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=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;begin assign(input,subset.in);reset(input);assign(output,subset.out);rewrite(output);while not eof dobegin read(n); s:=(n+1)*n shr 1; if s and 1=1 then writeln(0) else begin s:=s shr 1; for i:=1 to n do for j:=s downto i do fj:=fj+fj-i; writeln(fs shr 1); end; end;close(input);close(output);end.var f:array0.100000of int64; i,n,m,j:longint;begin assign(input,subset.in); reset(input); assign(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 do begin for j:=m-i downto 0 do fi+j:=fi+j+fj; fm=fm+fm-1 fm-1=fm-1+fm-2 end; writeln(fm div 2); close(output);end.动态规划一般解决两类问题，一类是最优化问题,就是问你最大价值最小数什么的，另一类是方案总数问题。/question/13759454.html滚动数组滚动数组就是动态规划时反复利用已开辟的空间，丢弃大量无用数组的方法作用是大规模动规时省内存常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DPij的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DPi,只需使用DPi - 1的信息，DPi - k,k1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DPij需要由DPi - 1 k,DPi - 2k决定，in，0k=10;n = 100000000;显然缩不成一维,正常我们应该开一个DP10000000511的数组，结果很明显，超内存（上百万就会超内存），其实我们只要开DP311就够了DPi%3j由DP(i - 1)%3k和DP(i - 2)%3k决定，空间复杂度差别巨大。不知道怎么说？举个例子d0 d1 d2 d3 d4 d5 d6 d7 d8 1 1 2 3 5 8 13 21 34d:array1.100 of integer;d0=1;d1=1;for(i=2;i100;i+) di=di-1+di-2;printf(%d,d99);上面这个循环di只依赖于前两个数据di-1和di-2;为了节约空间用滚动数组的做法d:array1.100 of integer;d0 d1 d2 d0 d1 d2 d0 d1 d2 1 1 2 3 5 8 13 21 34d0=1;d1=1;for(i=2;i100;i+) di%3=d(i-1)%3+d(i-2)%3;printf(%d,d99%3);注意上面的取余运算，我们成功地只保留了需要的最后3个解，数组好象在“滚动”一样，所以叫滚动数组对于二维也可以用（代码可能不太正确和完善，但是可以理解例子）:int i,j,d100100;for(i=1;i100;i+) for(j=0;j100;j+) dij=di-1j+dij-1;上面的dij只依赖于di-1j,dij-1;运用滚动数组int i,j,d2100;for(i=1;i100;i+) for(j=0;j100;j+)di%2j=d(i-1)%2j+di%2j-1;光光的作业（homework） 问题描述 光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k 小时。在长假前，老师们一共给光光布置了n 份作业，第i 份作业需要的时间是ti 小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当可能不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。 对于一件作业，只有2 种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第i 件作业如果没完成，就要受到pi 个单位的批评。 多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？ 输入 输入文件homework.in 包含以下内容：第一行只有一个数字k。第二行只有一个数字n。接下来n 行，每行两个数字，分别是ti 和pi， 两个数字之间用一个空格分开。 100%的数据中，k=100000，ti=10000，pi=10000； 30%的数据中，n=20； 100%的数据中，n=500。 输出 输出文件homework.out 仅包含一行，是一个数字，代表了光光最少受到的批评。 样例 homework.in 5 3 2 6 1 3 4 7 homework.out 6/bbs/read-oifans-tid-1487.html滚动数组例题：var f:array 0.1,0.100000 of longint; t,p:array 1.500 of integer; k,n,i,j,c,c2,pall:longint; begin /assign(input,homework.in); reset(input); /assign(output,homework.out); rewrte(output); readln(k); readln(n); pall:=0; fillchar(f,sizeof(f),0); for i:=1 to n do begin readln(ti,pi); pall:=pall+pi; for j:=ti to k do if f0,j0 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、ai+2、aj-1、aj分成p部分，怎样分？1in1jnikj-1 将ai、ai+1、ak 、 ak+1、ak+2aj 分成p-1部分 分成第p部分比如：把1、2、3、4、5、6分成2部分，12i4j6k 1 2 3 4 5 6第m部分 如果ai、ai+1、ak 、 ak+1、ak+2aj不在一条直线上，而是在圆周上，怎么划分呢？ m-1部分由 i. j组成。第m部分由1.i-1和j+1.n组成。m -1部分 for 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 for p:=2 to m-1 do 阶段：递推计算划分2部分m-1 部分的结果值 begin fillchar(fmax，sizeof(fmax)，0); 划分p 部分的状态转移方程初始化 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 决策：ai.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，jfmini，j)or(fmini，j0) then fmini，j:=fmin1i，k*gk+1，j; end;for fmin1:=fmin;fmax1:=fmax; end;formax:=0;min:=maxlongint; 将 a1、a2、an 划分成 m 个部分的最大值和最小值初始化if m=1 then 计算n 个数划分成一部分的最大值和最小值 begin max:=g1，n;min:=g1，n;endthen else for i:=1 to n do将a1ai-1、aj+1 an 设为第 m部分，计算最大值和最小值 for j:=i to n do if (i1) or (jn) then begin if (g1，i-1+gj+1，n) mod 10*fmax1i，jmax then max:=(g1，i-1+gj+1，n) mod 10*fmax1i，j; if(fmin1i，j=0) and (g1，i-1+gj+1，n) mod 10*fmin1i，jmin)then min:=(g1，i-1+gj+1，n) mod 10*fmin1i，j; end;then writeln(min); writeln(max); 输出最小值和最大值12i4j6k本题的计算过程分两个阶段 第一个阶段：将圆周上的 n 个数排成一个序列，计算 ai、ai+1、aj 划分成 m-1 个部分的最大值fmax1i，j和最小值fmin1i，j； 第二个阶段：将序列首尾相接。枚举第m 部分的所有可能情况，在fmax1和 fmin1的基础上，计算圆周上的n个数划分成m 个部分的最大值max 和最小值 min。 由于是一个圈,所以要从1-n中的每个点打断进行DP,最后统计最大最小值思考：能否将两个阶段合并，用一个状态转移方程来解决呢？请修改程序。6 mod 10=(-4) mod 10=6将N个数拉成2N个数的链，秒杀 var i,j,k,m,n,l,max,min,value:longint; a:array1.50of longint; sum:array0.100of longint; f,g:array1.50,1.10of longint;function min1(i,j:longint):longint;begin if ij then exit(i); exit(j);end;function get(i,j:longint):longint;2begin get:=sumj-sumi-1; if getfj,k then fj,k:=value*fl,k-1; if value*gl,k-1gj,k thengj,k:=value*fl,k-1 end; end; end; if maxgn,m then min:=gn,m; end; writeln(min);writeln(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; function 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); fillchar(b,sizeof(b),0); fillchar(f1,sizeo