《金明的预算方案》三种解法.docVIP

《金明的预算方案》的三种不同解法 湖北省襄樊市第五中学 杨兵 《金明的预算方案》是NOIP2006提高组的第二题。对于这道题，在此提供两种不同的解法与大家共同探讨。 一、转化为01背包问题 考虑到每个主件最多只有两个附件，因此我们可以通过转化，把原问题转化为01背包问题来解决，在用01背包之前我们需要对输入数据进行处理，把每一种物品归类，即：把每一个主件和它的附件看作一类物品。处理好之后，我们就可以使用01背包算法了。在取某件物品时，我们只需要从以下四种方案中取最大的那种方案：只取主件、取主件＋附件1、取主件＋附件2、既主件＋附件1＋附件2。很容易得到如下状态转移方程： f[i,j]=max{f[i-1,j]， f[i-1,j-a[i,0]]+a[i,0]*b[i,0]， f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]， f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]， f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2]} 其中，f[i,j]表示用j元钱，买前i类物品，所得的最大值，a[i,0]表示第i类物品主件的价格，a[i,1]表示第i类物品第1个附件的价格，a[i,2]表示第i类物品第2个附件的价格，b[i,0],b[i,1],b[i,2]分别表示主件、第1个附件和第2个附件的重要度。f[i-1,j]表示把j元钱全部投入前i-1类物品所得的最大值，即不取第i类物品这一方案，f[i-1,j-a[i,0]]+a[i,0]*b[i,0]表示只取第i类物品的主件这一方案，f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]，表示取第i类物品的主件和第１个附件这一方案，f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]，表示取第i类物品的主件和第2个附件这一方案，f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2]，则表示取第i类物品的主件和两个附件这一方案。 参考代码如下： program budget; var a:array[1..60,0..3] of integer;//a数组用来存放每一类物品，a[i,3]用来保存每类物品主件的编号 b:array[1..60,0..2] of integer; f:array[0..60,0..3200] of integer; n,m,i,s,v,p,q,j:integer; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); assign(input,budget.in); assign(output,budget.out); reset(input); rewrite(output); readln(n,m); n:=n div 10; s:=0; for i:=1 to m do begin readln(v,p,q);//读入数据 v:=v div 10;//优化，因为每个物品的价格是10的整数倍 if q=0 then begin//主件 inc(s); a[s,0]:=v; a[s,3]:=i; b[s,0]:=p; end else begin//是附件 for j:=1 to s do//此循环用来查找该附件的主件，找到后就退出循环 if a[j,3]=q then break; if a[j,1]=0 then begin a[j,1]:=v;b[j,1]:=p; end else begin a[j,2]:=v;b[j,2]:=p; end; end; end; fillchar(f,sizeof(f),0);