06普及组开心的金明程序思路
题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。优化空间复杂度以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。procedure ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight}注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。有了这个过程以后,01背包问题的伪代码就可以这样写:for i=1..N ZeroOnePack(c[i],w[i]);初始化的细节问题我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。小结01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。
开心的金明:
pascal源程序:
program aaa;
var
v,p:array [1..60] of longint;{v:价值,p:重量}
f:array [0..60,0..32000] of longint;
i,j,n,m:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a
else max:=b;
end;
begin
readln(n,m);
fillchar(q,sizeof(q),false);
for i:=1 to m do
readln(v[i],p[i]);
for i:=1 to m do
for j:=0 to n do
begin
if (v[i]<=j) then
f[i,j]:=max(f[i-1,j],f[i-1,j-v[i]]+v[i]*p[i]){动态规划转移方程}
else f[i,j]:=f[i-1,j];
end;
writeln(f[m,n]);
end.
在历届NOIP竞赛中,有4道初赛题和5道复赛题均涉及到背包问题,所谓的背包问题,可以描述如下:一个小偷打劫一个保险箱,发现柜子里有N类不同大小与价值的物品,但小偷只有一个容积为M的背包来装东西,背包问题就是要找出一个小偷选择所偷物品的组合,以使偷走的物品总价值最大。
如有4件物品,容积分别为: 3 4 5 8
对应的价值分别为: 4 5 7 10
小偷背包的载重量为:12
则取编号为1 2 3的物品,得到最大价值为16。
算法分析:如果采用贪心法,则先取价值最大的10,消耗了容积8,下面只能取容积为4的物品,得到价值5,这样总价值是15,这不是最优解,因此贪心法是不正确的。
采用穷举法,用一个B数组来表示取数的标记,当B[i]=0时表示第i件物品不取,当B[i]=1时表示第i件物品已取,初始化全部取0,以下算法是从后面的物品开始取起,通过B数组的取值把15种取法全部穷举出来,价值MAX初始化为0。
B[0] B[1] B[2] B[3] B[4]
0 0 0 0 0 {初始化}
0 0 0 0 1 {取第4件物品,容积为8,不超,价值为10,将MAX替换为10}
0 0 0 1 0 {取物品3,容积为5,不超,价值为7,不换}
0 0 0 1 1 {取物品3、4,容积为13,超}
0 0 1 0 0 {取物品2,容积为4,不超,价值为5,不换}
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
……
0 1 1 1 0 {这是最佳方案}
0 1 1 1 1
1 0 0 0 0 {当B〔0〕=1时停止,B〔0〕称为哨兵}
生成B数组中数据的方法如下:
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do
b[i]:=0;
end;
小结:以上每件物品只能取1件,所以取法只有0和1两种情况,我们称之为0、1背包,算法的时间复杂度为O(2N),在1秒内N只能做到20。
例1:选数(NOIP2002 初中组复赛第2题)
[问题描述]:已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29。
[输入]:
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
n[输出]:
屏幕输出,格式为:
一个整数(满足条件的种数)。
[输入输出样例]:
输入:
4 3
3 7 12 19
输出:
1
[算法分析]:本题应用背包问题中取数的方法进行穷举,在取数的过程中,当B数组中有K个1的时候将对应的K个数相加,再判断是不是素数。
主要程序段如下:
readln(n,k); sum:=0;
for i:=1 to n do read(a[i]);
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do b[i]:=0;
m:=0;
for i:=1 to n do
if b[i]=1 then m:=m+1; {统计1的个数}
if m=k then
begin 计算此种取数方法得到的和S;
if S 是素数 then sum:=sum+1;
end;
end;
例2:采药(NOIP2005 初中组复赛第3题)
【问题描述】
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
【输入文件】
输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据,M <= 10;
对于全部的数据,M <= 100。
【算法分析】本题如果采用上述方法来解,只能将M算到20,而这里M〈=100,所以只能拿30%的分数,比较好的算法是采用动态规划,为了能说清算法,现重新举一个例子,若输入:
10 3
3 4
4 5
5 6
表示背包的容量是10,有3种物品。用一个数组用来表示背包容量与其最大价值的关系,上例中设置一个数组count,用下标表示容量,初始化为0。然后按物品的顺序一一来统计此时的最大价值,每种药品对应各种背包容量时得到的最大价值为:
对于是第i件物品,背包容量为j时的最大价值Cmax(j)=MAX(Cmaxj,Pi+余下空间的最大价值Cmax(j-i物品所占的空间)),如上例中,根据物品的不断增加,各容量背包得到的最大价值不断替换:
容量 1 2 3 4 5 6 7 8 9 10
价值
序号 0 0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4 4 4 4
2 0 0 4 5 5 5 9 9 9 9
3 0 0 4 5 6 6 9 10 11 11
[数据结构] time,price数组分别用来存入时间和价值,count来存入背包的价值。
var
time,price:array[1..100] of longint;
t:longint; i,m,j:integer;
count:array[0..1000] of longint;
begin
assign(input,'medic.in');
assign(output,'medic.out');
reset(input);
rewrite(output);
readln(t,m);
for i:=1 to m do
readln(time[i],price[i]);
fillchar(count,sizeof(count),0);
for i:=1 to m do
for j:=t downto 1 do
begin
if (j>=time[i]) and (price[i]+count[j-time[i]]>count[j]) then
count[j]:=price[i]+count[j-time[i]];
end; {j>=time[i]表示当前的容量能放入背包,price[i]+count[j-time[i]]>count[j]表示第i件物品的价值加上第i件物品对于背包容量为j时余下空间的最大价值大于当前背包容量为j时的最大价值}
writeln(count[t]);
close(input);
close(output);
end.
例3:开心的金明(NOIP2006 初中组复赛第2题)
题目较长,省略,本题与例2相比,在比较时要先将价值乘以一个数,其余一样,但要注意的是:本题N的范围是<=26,如果用0、1背包穷举法在1秒内只能过10个点中的8个点。
总结:采用动态规划的时间复杂度为O(n*m),范围比穷举法大多了,但也有弱点,当数据不是整数时,就不可使用;如果还要求出具体的取法,那也相当麻烦。
DP,0-1背包问题.
把总钱数看作背包可容重量.
把希望购买物品的个数看作要放进背包的物品的数量.
把物品的价格看作物品的重量.
把物品的价格与物品的重要度的乘积看作物品的价值.
i:前i个物品 j:背包剩余可容重量 w:第i个物品的重量 r:第i个物品的价值
i=0 f[i,j]=0
i>0 f[i,j]=max{f[i-1,j],f[i-1,j-w]+r}
program happy(input,output);
var
i,j,m,n:longint;
w,r:array[1..25] of longint;
a:array[0..1,-10000..100000] of longint;
begin
assign(input,'happy.in');reset(input);
assign(output,'happy.out');rewrite(output);
read(n,m);
for i:=1 to m do
begin
read(w,r);
r:=r*w;
end;
for i:=1 to m do
begin
a[1]:=a[0];
for j:=w to n do
if a[0,j-w]+r>a[1,j] then a[1,j]:=a[0,j-w]+r;
a[0]:=a[1];
end;
writeln(a[1,n]);
close(input);close(output);
end.
(参见经典0-1背包-采药)
把0-1背包问题一改就行了 只是把加的 重量 改成 价值与重要度的乘积 !
program happy;
var
f:array[0..25,0..30000] of longint;
i,j:integer;
n,m:longint;
v,p:array[1..25] of longint;
begin
readln(m,n);
for i:=1 to n do
read(v[i],p[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to m do
begin
f[i,j]:=f[i-1,j];
if (j>=v[i])and(f[i,j]<f[i-1,j-v[i]]+p[i]*v[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i]*v[i];
end;
writeln(f[n,m]);
end.
典型的01背包问题,时间复杂度为O(Nm)。
一种做法是使用滚动数组,每次可以从前往后更新,也可以从后往前更新;另一种是只使用一个一维数组,每次只能从后往前更新。
在表示状态的时候,可以用f[i]表示正好花了i元,能够得到的最大总和;也可以用f[i]表示花了不超过i元,能够得到的最大总和。
程序1:滚动数组+表示正好
var
n,m,i,j,ans:longint;
a:array[0..25,0..2] of longint;
dp,dp2:array[0..30000] of longint;
begin
assign(input,'happy.in'); reset(input);
assign(output,'happy.out'); rewrite(output);
fillchar(a,sizeof(a),0);
read(n,m);
for i:=1 to m do begin
read(a[i,0],a[i,1]); {输入价格和重要程度}
a[i,2]:=a[i,0]*a[i,1]; {计算乘积}
end;
fillchar(dp2,sizeof(dp2),$FF); {初始时dp[i]=-1,i>0,表示正好花i元得不到任何总和}
dp2[0]:=0; {只有dp[0]=0,因为正好花了0元,得到的总和为0}
for i:=1 to m do begin
dp:=dp2; {以后用dp来推dp2}
for j:=0 to n do {枚举花了j元钱}
if (dp[j]>-1) and (j+a[i,0]<=n) and (dp2[j+a[i,0]]<dp[j]+a[i,2]) then {j元钱的方案存在,加上这次的价格没有超过可用的n元,并且这个方案得到的总和更大,就更新}
dp2[j+a[i,0]]:=dp[j]+a[i,2];
end;
ans:=-1; {求dp2中的最大值}
for i:=0 to n do
if dp2[i]>ans then ans:=dp2[i];
writeln(ans);
close(input); close(output);
end.
程序2:单个一维数组+表示不超过
var
n,m,i,j:longint;
a:array[0..25,0..2] of longint;
dp:array[0..30000] of longint;
begin
assign(input,'happy.in'); reset(input);
assign(output,'happy.out'); rewrite(output);
fillchar(a,sizeof(a),0);
read(n,m);
for i:=1 to m do begin
read(a[i,0],a[i,1]); {输入价格和重要程度}
a[i,2]:=a[i,0]*a[i,1]; {计算乘积}
end;
fillchar(dp,sizeof(dp),0); {初始时dp[i]=0,表示花不超过i元可以得到0总和}
for i:=1 to m do
for j:=n downto 0 do {从后往前枚举花了j元钱}
if (j+a[i,0]<=n) and (dp[j+a[i,0]]<dp[j]+a[i,2]) then {加上这次的价格没有超过可用的n元,并且这个方案得到的总和更大,就更新}
dp[j+a[i,0]]:=dp[j]+a[i,2];
writeln(dp[n]); {输出最后花不超过n元能得到的最大总和}
close(input); close(output);
end.
06普及组开心的金明程序思路
小结:以上每件物品只能取1件,所以取法只有0和1两种情况,我们称之为0、1背包,算法的时间复杂度为O(2N),在1秒内N只能做到20。例1:选数(NOIP2002 初中组复赛第2题)[问题描述]:已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一...
NOIP2006普及组开心的金明
太水了!只不过是一个0\/1背包问题而已,例程给的太繁琐了,我现编的一个版本,AC所有数据。program happy(input,output);const maxn=30001;maxm=25;var a:array[0..maxn]of longint;v,w:array[0..maxm]of longint;n,m,i,j:longint;procedure readdata;begin assign(input,'happy.in'...
求第十二届全国青少年奥林匹克信息学联赛(普及组PASCAL语言)复赛试题...
15 20 32 40 67 89 300 400 2.开心的金明 (happy.pas\/c\/cpp)【问题描述】金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始...
noip2006普及组测评数据
告诉我你的邮箱,我给你发过去 陶陶摘苹果 开心的金明 jam的计数法 循环 也可到oifans上去下载 参考资料:noip 组委会
NOIP2008快到了
1)背包类(01年普及组《装箱问题》、05普及组《采药》,06年普及组《开心的金明》、06年提高组《金明的预算方案》)2)简单树状(03年《加分二叉树》)3)最长XX子序列(04年提高组《合唱队形》、99年提高组《拦截导弹》)4)矩阵连乘&石子归并(06年提高组《能量项链》)5)圆环取数类(03年...
池鲁苯丙: 输出文件happy.out只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(
凌源市18156132064: NOIP2006普及组开心的金明 - ?
池鲁苯丙: 太水了!只不过是一个0/1背包问题而已,例程给的太繁琐了,我现编的一个版本,AC所有数据.program happy(input,output); const maxn=30001;maxm=25; var a:array[0..maxn]of longint; v,w:array[0..maxm]of longint; n,m,i,j:longint; procedure ...
凌源市18156132064: pascal 谁可以讲解一下这个开心的金明这个简短的程序(精讲) - ?
池鲁苯丙: 题目有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使价值总和最大.基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放.用子问题定义状态:即f[i][v]表示前i件...
凌源市18156132064: 开心的金明的动态转移方程怎么推的 - ?
池鲁苯丙: 开心的金明是一个01背包问题,你先要把所有的主要物品的所有情况都要考虑,所以可以放的物品的数量就变成了所有的情况,即一个主要物品物品分别带0、1、2...个物品,每种组合就是算成一个物品(这是个预处理),这个处理完后,就可以使用熟知的01背包问题的动态规划方程(也就是f[i,j]=max[f[i-1,j],f[i-1,j-c[i]]+c[i]*v[i]])了.
凌源市18156132064: pascal开心的金明 动态规划做. - ?
池鲁苯丙: 楼上的空间可能会爆,有一维的解法varn,m,i,j,k,x:longint;v,p:array[0..25]of longint;f:array[0..30000] of longint;function max(a,b:longint):longint;beginif a>b then exit(a...
凌源市18156132064: pascal 题目问题(开心的金明) - ?
池鲁苯丙: var n,m,i,j,k,x:longint; v,p:array[0..25]of longint; f:array[0..30000] of longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin readln(n,m); for i:=1 to m do readln(v[i],p[i]); for i:=1 to m do for j:=n downto v[i] do f[j]:=max(f[j],f[j-v[i]]+p[i]*v[i]); write(f[n]); end.
凌源市18156132064: happy解释(2007NOIP题目"开心的金明") - ?
池鲁苯丙: 背包问题 *部分背包问题可有贪心法求解:计算Pi/Wi 数据结构: w[i]:第i个背包的重量; p[i]:第i个背包的价值; 1.0-1背包: 每个背包只能使用一次或有限次(可转化为一次): A.求最多可放入的重量. NOIP2001 装箱问题(跟这个是一个模...
凌源市18156132064: Pascal开心的金明 - ?
池鲁苯丙: 01背包 var f:array[0..1,0..100000]of longint; n,m,i,j,w,r:longint; begin assign(input,'happy.in');reset(input); assign(output,'happy.out');rewrite(output); readln(n,m); for i:=1 to m do begin read(w,r); f[0]:=f[1]; for j:=1 to n do if (j>=w)and(f[0,j-w]+w*r>f[0,j])...
凌源市18156132064: noip2006 pascal普及组第四题数列,我获取到一个人编写的程序,且经测试所有测试点正确,请帮忙解释以下. - ?
池鲁苯丙: 1,3,4,9,10,12,13,… (该序列实际上就是:30,31,30+31,32,30+32,31+32,30+31+32,…) 这道题关键要找规律1,30是3的0次方,31是3的2次方,如此类推2,找出n和3的幂之间的规律 n=1时(换成2进制数为1),他的值为等于3的0次方 n=2时(...
凌源市18156132064: free pascal 开心的金明 (高人来指点)?
池鲁苯丙:for i:=1 to m do begin for j:=n downto v[i] do s[j]:=max(s[j],s[j-v[i]]+a[i]); end; s[j]表示用j元钱,可以买到的最大重要度 i的循环表示依次物品放入数组,重要度大的覆盖重要度小的. 注意 j 是倒叙,为避免在放入第i个物品时改变s[x]的值而带动后面的值改变