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

《《金明的预算方案》三种解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《金明的预算方案》的三种不同解法湖北省襄樊市第五中学杨兵《金明的预算方案》是NOIP2006提高组的第二题。对于这道题，在此提供两种不同的解法与大家共同探讨。一、转化为01背包问题考虑到每个主件最多只有两个附件，因此我们可以通过转化，把原问题转化为01背包问题来解决，在用01背包之前我们需要对输入数据进行处理，把每一种物品归类，即：把每一个主件和它的附件看作一类物品。处理好之后，我们就可以使用01背包算法了。在取某件物品时，我们只需要从以下四种方案中取最大的那种方案：只取主件、取主件＋附件1、取主件＋附件2、

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,

3、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]+

4、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类物品的主件和两个附件这一方案。参考代码如下：programbudget;vara:array[1..60,0..3]ofinteger;/

5、/a数组用来存放每一类物品，a[i,3]用来保存每类物品主件的编号b:array[1..60,0..2]ofinteger;f:array[0..60,0..3200]ofinteger;n,m,i,s,v,p,q,j:integer;beginfillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);assign(input,'budget.in');assign(output,'budget.out');reset(input);rewrite(output);rea

6、dln(n,m);n:=ndiv10;s:=0;fori:=1tomdobeginreadln(v,p,q);//读入数据v:=vdiv10;//优化，因为每个物品的价格是10的整数倍ifq=0thenbegin//主件inc(s);a[s,0]:=v;a[s,3]:=i;b[s,0]:=p;endelsebegin//是附件forj:=1tosdo//此循环用来查找该附件的主件，找到后就退出循环ifa[j,3]=qthenbreak;ifa[j,1]=0thenbegina[j,1]:=v;b[j,1]:=

7、p;endelsebegina[j,2]:=v;b[j,2]:=p;end;end;end;fillchar(f,sizeof(f),0);m:=s;//处理完输入数据后，s为共有多少类物品fori:=1tomdo//对m类物品进行动态规划，枚举物品forj:=0tondo//枚举状态begin//找最优的方案f[i,j]:=f[i-1,j];//不取第i类物品if(j>=a[i,0])and(f[i,j]

8、[i,0]]+a[i,0]*b[i,0];if(j>=(a[i,0]+a[i,1]))and(f[i,j]=(a[i,0]+a[i,2]))and(f[i,j]<