06普及组开心的金明程序思路

pascal 谁可以讲解一下这个开心的金明这个简短的程序（精讲）~

题目有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.

---

凌源市18156132064： 【NOIP2006普及组】开心的金明C语言解法 - ？
池鲁苯丙： 输出文件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]的值而带动后面的值改变