宠物(解题报告).ppt

《宠物(解题报告).ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、From：徐钧鸿WhiteξLight宠物问题回顾宠物店里有N只宠物，第i只宠物每天固定要吃hunger[i]单位食物。现在FJ每天的食物只有totalFood，他想买尽量多的宠物，并且把它们放在一个笼子里养。但是有个问题，第i个宠物看到别的宠物吃东西时，它就变得贪吃，于是它每天会要求吃额外的食物，食物的数量等于和它在同一个笼子里的其它宠物的数量*greed[i].那么FJ最多可以买多少只宠物放在同一个笼子里面养？输入输出输入格式：多组测试数据。第一行：一个整数t。1<=t<=5.每组测试数据的格式：第一行：两个整数，N和totalFood。1<=N<=50;1<=totalFoo

2、d<=10^6.第二行：N个整数，表示hunger[i]。1<=hunger[i]<=1000.第三行：N个整数，表示greed[i]。0<=greed[i]<=1000.输出格式：共t行，每行一个整数，表示最多可以买多少只宠物。样例数据输入样例：pet.in23712322141952150241输出样例：pet.out23样例说明：可以选择买宠物1、2、4。由于笼子里有三只宠物，那么宠物1每天要吃5+(3-1)*0=5单位食物，宠物2每天要吃2+(3-1)*2=6单位食物，宠物4每天要吃5+(3-1)*1=7单位食物，三只宠物每天总共要吃18个单位食物，FJ可以应付。（对第二组

3、数据的说明）算法分析看上去第一眼动规，最后动着动着就死在里面了。其实这道题动规还真不太好办（我至今没想出好的办法，但也不敢说真的不可以）。刚开始的思路是以totalFood为背包容量，记录每一个容量时宠物数最大。但是可以看一眼方程：c[i]:=max(c[i-h[j]+g[j]*d])+1（i是粮食数，j是宠物号）方程中的字母d指宠物数量，而他的表达式是c[i-h[j]+g[j]*d]还有d，这样就不断循环下去，根本无法出解。所以以totalFood为背包容量动规基本不行。其实这道题用贪心就可以ac。方法如下：首先先计算出每一只宠物j在有i只宠物时消耗的食物数量，记录为吧b[i,j

4、]。之后每一种宠物数量进行排序。再从宠物数量大的找，输出前k个（宠物数为k)，如果加起来的值不超过totalFood，就输出k。参考程序varn,tf,t:longint;g,h:array[1..50]oflongint;b:array[0..50,1..50]oflongint;f:boolean;i,j,k,iii,total,temp:longint;beginreadln(t);foriii:=1totdobeginreadln(n,tf);fori:=1tondoread(h[i]);readln;fori:=1tondoread(g[i]);readln;fori:=

5、1tondoforj:=1tondob[i,j]:=h[j]+g[j]*(i-1);fori:=ndownto0dobeginforj:=1ton-1dofork:=jtondoif(b[i,j]>b[i,k])thenbeginb[i,j]:=b[i,j]xorb[i,k];b[i,k]:=b[i,j]xorb[i,k];b[i,j]:=b[i,j]xorb[i,k];end;f:=true;k:=0;forj:=1toidobegink:=k+b[i,j];if(k>tf)thenbeginf:=false;break;end;end;iffthenbeginwriteln(i

6、);break;end;end;end;end.本程序已经过清橙检测，请放心copy。谢谢围观