背包问题培训学案

背包问题（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