冬令营作业kfc解题报告

1、KFC (K. Fried Chicken)解题原题回顾Jackson是江苏某中学高一的一名学生，他天资聪明，勤奋好学，经常在不经意间获得省、市的数学、物理、化学、计算机等竞赛的一等奖。但是，思维高度如同珠穆朗玛峰一般高的他却总是不屑于处理自己身边的一些琐碎的小事。于是，他雇佣了你当他的，你需要完成如下任务。那是一个寒风凛冽的夜晚，Jackson仍然在电脑前奋力地工作着。这时他突然喊到身边他饿了，他想让你到KFC买些东西给他吃。于是他给了你K块钱。你很快来到KFC的店里，看到屏幕上写着为1.n的每种食物的单价，以及各种套餐的组合形式和套餐的价格。这是你想起了Jackson 的嘱咐：最多花K元，

2、买的食物的种类要尽可能多，当种类数一定时，买的食物的单价和越大越好。（每种食物可以买任意多份）你可以用计算机帮你完成这个任务解题分析这道题目看似包装得很生活化，无从下手，但当看到了“K 块钱”这几个字眼，你就应该联想到了背包问题。同样是给定了某一个数据的范围，只要把这“K 块钱”当作一个背包，事物看作带权值的物品，进行一次“背包问题”即可。当然，在想不到以上方法的时候，A*搜索也是种很实惠的算法。算法描述算法的基本是这样的：列一张 1.n 的 HASH 表 r。ri表示用 i 块可以达到的最大种类和最大单价和等情况。具体算法如下：i 为 01、 判断 i 这个价格能否达到，若不能，则 GOTO

3、 32、 （即能达到i 这个价格），把每一种物品或套餐的价格分别加上 i，假设得到 t。把 rt所达到的物品种类最大值，与 ri所的物品和新加的物品的总和的物品种类数对比。取一个大的。若两数相等，则再比较两种情况下的单价总和。3、 i:=i+1。 如果 ik，那么 END。 GOTO 1。输入输出输入：第一行是整数 K，N，M （N 表示食物的种类数，M 表示套餐的种类数）第 2N+1 行每行一个整数 ai表示第 i 种食物的单价第 N+2N+M+1 行每行开头一个整数 pj表示第 j 种套餐包含的食物数，接下来 pj个整数表示第 j 中套餐中包含的食物的。再接下来一个整数 mj表示这种套餐所

4、需的价钱。输出一行，两个整数 Z，T，分别表示所买食物种类数和所买食物的单价总和。（两个整数间用两个空格隔开，行末不要有多余空格）数据结构k,n,m,i,j,w,t,z,s:long;r,a:array0.1000of alex; r 即为 HASH 表；a 为各物品的单价，也是 r 的初始值:array1.1000of 0.1; 两者皆为某一种食物是否存在程序剖析typealex=array-2.100of long;vark,n,m,i,j,w,t,z,s:long;r,a:array0.1000of alex;:array1.1000of 0.1;procedure qsort(l,r:

5、longvar);快速排序i,j,x:long y:alex;begin;i:=l;j:=r;x:=a(l+r) div 2,-1; while i=j dobeginwhile (i=j)and(ai,-1x)while (ix) if i=j thenbeginy:=ai; ai:=aj; aj:=y;inc(i);dec(j); end;end;if ir then qsort(i,r); if lk),0);do枚举每一种的食物或套餐then break;超出范围for w:=1 to aj,0 faj,w:=1;s:=0;do标记已有食物for w:=1 to n s:=s+fw; t:=i+aj,-1;if (rt,0rt,-1)beginthenrt,-2:=1;此价格可以达到rt,-1:=ri,-1+aj,-2;rt,0:=0;单价和for w:=1 toif fw=1n dothen具体情况 begininc(rt,0);rt,rt,0:=w; end;end;end;end;z:=0; t:=0;for i:=k downto if (ri,0z)寻找最大值1 door (ri,0=z) and (ri,-1t)then begin z:=ri,0; t:=ri,-1; end;wrin(z, ,t);打印close(output);end.样例