程序设计贪心算法

《程序设计贪心算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告2011・2012学年第_2_学期任课老师：课程名称班级座号姓名实验题目贪心算法设计技术的应用实验时间实验开始日期：2012.4.20报告提交日期：2012.4.30实验目的、要求一、实验题目1.利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi,它的总价值为Pi,假定M、W'i、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。2.设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100,20,10,5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种

2、所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。二、实验要求1.该实验的课内学时是4个课吋。2.题目1必须完成。3.题Fl1在完成上述基本功能的前提下，有能力的同学可以完成题目2。实验步骤与内容(t)实验叔针的數据無枸数组floatP[20],W[20],value[20],x[20];①背包voidpackbag()inti,j,n,s二0;floatP[20],W[20],value[20],x[20],values二0;floatq二0,t二0,M二0;printfC请盛人货物的数目n:rT);scanf("%d",&n);p

3、rintfC请输入背包的负重M:rT);scanf("%f",&M);printfC请输入各种货物的重量:〃)；for(i=l;i<=n;i++)scanf(%f〃,&W[i]);printff请输入各种货物的价值:〃)；for(i=l;i<=n;i++)scanf(饨f",&P[i]);for(i=l;i<=n;i++)value[i]=P[i]/W[i];//计算货物的单位重量价值for(i=l;i<=n;i++){for(j=l;jE-i;j++)if(value[j]

4、j+l];value[j+l]=t;〃按货物的单位重量价值进行排序q二W[j];W[j]岬[j+1];W[j+1]二q;//相应的货物重量进行排序}}printfC单位价值量(从大到小)如下：");for(i=l;i〈=n;i++)printf(，z%5.2fvalueti]);printf("");printff所对应的货物重量如下:『);for(i=l;i<=n;i++)printfC%5.2f",W[i]);printfU");i=l；while(M!=0){M-二W[i];//背包负重递减values二values+w[i]*value[

5、i];//计算总价值x[i]二W[i];s二i;s++;if(M<=W[s]){values二values+M*value[s];//如果背包的负重小于货物的重量时,则装货量等于背包的剩奈载重xL++iJ=M;M=0;i++；printf(装货方式如下：);for(i=l;i〈=n;i++)printf(，z%5.2f"、x[i]);printf;printf("最大价值为:values=%5.2f",values);}printf;②收银系统voidmoneysys()doubleprice,total=0,givemoney,leamoney;in

6、tn,i,k=0,m=0,x=0,y=0;printfC请输入商品的数目：〃);scanf&n);printf(/z输入每彳牛商品的价格:〃)；for(i=l;i<=n;i++){printf(，z第％(1件："，i);seanf&price);total二total+price;}printfC"总的价格=%5.2frT,total);printfC'输入颇孝所给的钱:〃)；seanf(〃％1产,&givemoney);leamoney=givemoney-totai;printf余的钱为%5.2f，z,leamoney);printfC#

7、种货币药薮自如卞:;whi1e(1eamoney>=100){1eamoney=learnoney-100;k++;if(1eamoney<100)}printf(，z100元二%d张",k);while(leamoney>=20)1eamoney=learnoney-20;x++;if(leamoney<20)printf(z，20元或d张x);while(1eamoney>=10){leamoney=leamoney-10;printf(〃1070=1张〃);}.while(1eamoney>=5){1eamoney=learnoney-5;}

8、printf("5元二1张?，);