背包问题(2)2010年3月11日晚培训内容:1、砝码称重的背包解法。2、SubsetSums集合的背包解法。3、数字游戏。4、滚动数组的应用。砝码称重的背包解法【问题分析】11122333把问题稍做一个改动,已知a1+a2+a3+a4+a5+a6个砝码的重量w[i],w[i]∈{1,2,3,5,10,20}其中砝码重量可以相等,求用这些砝码可称出的不同重量的个数。这样一改就是经典的0/1背包问题的简化版了。把a1个砝码看成0/1背包中的第1个物品,重量与价值均为a1*1。把a2个砝码看成0/1背包中的第2个物品,重量与价值均为a2*2。只是要注意这个题目不是求最大载重量,是统计所有的可称出的重量的个数。:array[1..6]of1..20=(1,2,3,5,10,20);maxll=1001;vari,j:longint;a,b:array[1..10]oflongint;f:array[1..1001]oflongint;beginfori:=1to6dobeginread(a[i]);b[i]:=a[i]*w[i];end;readln;fori:=1to6dobeginforj:=maxlldowntob[i]dobeginiff[j-b[i]]+b[i]f[j]thenf[j]:=f[j-b[i]]+b[i];{体积与价值相同}end;end;writeln(f[maxll]);{maxll能达到多少就有多少种重量}end.砝码称重的测试数据如下:4.1110000Total=34.2220000Total=64.3103000Total=74.4340500Total=364.5222222Total=824.6032745Total=1854.7063421Total=794.8123456Total=2044.8654321Total=834.101010101011Total=140SubsetSums集合背包解法集合对于从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。程序不能预存结果直接输出。PROGRAMNAME:subsetINPUTFORMAT输入文件只有一行,且只有一个整数NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT输出划分方案总数,如果不存在则输出0。SAMPLEOUTPUT(filesubset.out)4当1到n的总和为奇数时,一定没有一种方案,可以直接输出0,否则把总和div2当作背包的容量,用1到n个数去做0/1背包,把每一种情况加起来,状态方程:f[j]=f[j]+f[j-i],由于n个数都使用了两次,所以情况总数也就是答案的2倍,所以输出时div2就可以了。不知道为什么的请看下面:如n=3时,s=3;集合有[{1,2}和{3},{3}和{1,2}]这样就重复了,所以div2。f[j]集合的是由{j-i}和{i}组合的.f[j-i]有几种情况,那j-i和i的组合就有几种情况了,这是加法原理。}programsubset;varn,i,j:longint;s:int64;st:array[0..390]ofint64;beginassign(input,'subset.in');reset(input);assign(output,'subset.out');rewrite(output);whilenoteofdobeginread(n);s:=(n+1)*nshr1;ifsand1=1thenwriteln(0)elsebegins:=sshr1;fori:=1tondoforj:=sdowntoidof[j]:=f[j]+f[j-i];writeln(f[s]shr1);end;end;close(input);close(output);end.varf:array[0..100000]ofint64;i,n,m,j:longint;beginassign(input,'subset.in');reset(input);assign(output,'subset.out');rewrite(output);readln(n);close(input);m:=(1+n)*ndiv2;ifmmod2=1thenbeginwriteln('0');close(output);halt;end;m:=mdiv2;f[0]:=1;fori:=1tondobeginforj:=m-idownto0dof[i+j]:=f[i+j]+f[j];{f[m]=f[m]+f[m-1]f[m-1]=f[m-1]+f[m-2]}end;writeln(f[m]div2);close(output);end.动态规划一般解决两类问题,一类是最优化问题,就是问你最大价值最小数什么的,另一类是方案总数问题。滚动数组滚动数组就是动态规划时反复利用已开辟的空间,丢弃大量无用数组的方法作用是大规模动规时省内存常用于DP之中,在DP过程中,我们在由一个状态转向另一个状态时,很可能之前存储的某些状态信息就已经无用了,例如在01背包问题中,从理解角度讲我们应开DP[i][j]的二维数组,第一维我们存处理到第几个物品,也就是阶段了,第二维存储容量,但是我们获得DP[i],只需使用DP[i-1]的信息,DP[i-k],k1都成了无用空间,因此我们可以将数组开成一维就行,迭代更新数组中内容,滚动数组也是这个原理,目的也一样,不过这时候的问题常常是不可能缩成一维的了,比如一个DP[i][j]需要由DP[i-1][k],DP[i-2][k]决定,in,0k=10;n=100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组,结果很明显,超内存(上百万就会超内存),其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i-1)%3][k]和DP[(i-2)%3][k]决定,空间复杂度差别巨大。不知道怎么说?举个例子d:array[1..100]ofinteger;d[0]=1;d[1]=1;for(i=2;i100;i++)d[i]=d[i-1]+d[i-2];printf(%d,d[99]);上面这个循环d[i]只依赖于前两个数据d[i-1]和d[i-2];为了节约空间用滚动数组的做法d:array[1..100]ofinteger;d[0]=1;d[1]=1;for(i=2;i100;i++)d[i%3]=d[(i-1)%3]+d[(i-2)%3];printf(%d,d[99%3]);注意上面的取余运算,我们成功地只保留了需要的最后3个解,数组好象在“滚动”一样,所以叫滚动数组对于二维也可以用(代码可能不太正确和完善,但是可以理解例子):inti,j,d[100][100];for(i=1;i100;i++)for(j=0;j100;j++)d[i][j]=d[i-1][j]+d[i][j-1];上面的d[i][j]只依赖于d[i-1][j],d[i][j-1];运用滚动数组inti,,j,d[2][100];for(i=1;i100;i++)for(j=0;j100;j++)d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];光光的作业(homework)[问题描述]光光上了高中,科目增多了。在长假里,光光的老师们都非常严厉,都给他布置了一定量的作业。假期里,光光一共有的时间是k小时。在长假前,老师们一共给光光布置了n份作业,第i份作业需要的时间是ti小时。但是由于老师们互相不商量,因此光光有可能不能完成老师的作业。当可能不能完成老师的作业时,光光就事后去向老师说明,然后被老师批评一顿了事。对于一件作业,只有2种情况:完成或者不完成(快要完成也算不完成)。如果没完成,d[0]d[1]d[2]d[0]d[1]d[2]d[0]d[1]d[2]112358132134d[0]d[1]d[2]d[3]d[4]d[5]d[6]d[7]d[8]112358132134受到批评是天经地义的。但是,不同的作业对于光光来说,批评的力度是不同的。第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.in53261347homework.out6滚动数组例题:varf:array[0..1,0..100000]oflongint;t,p:array[1..500]ofinteger;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);fori:=1tondobeginreadln(t[i],p[i]);pall:=pall+p[i];forj:=t[i]tokdoiff[0,j]p[i]thenf[0,j]:=p[i];end;c:=0;fori:=1tondobeginc:=1-c;forj:=1tokdobeginf[c,j]:=f[c,j-1];ifj-t[i]0theniff[1-c,j-t[i]]+p[i]f[c,j]thenf[c,j]:=f[1-c,j-t[i]]+p[i];(mod2)end;end;writeln(pall-f[c,k]);//close(input);close(output);end.1、P34:数字游戏要求:能读懂该程序;能回答该题后面提出的一个问题:把两阶段的程序段合并成一段。思考:如果要将ai、ai+1、ai+2……、aj-1、aj分成p部分,怎样分?将ai、ai+1……、ak、ak+1、ak