文档介绍：:..实验报告2011 ・ 2012 学年第_2_学期任课老师: 课程名称班级座号姓名实验题目贪心算法设计技术的应用实验时间实验开始日期::、要求一、 。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi,它的总价值为Pi,假定M、W'i、Pi均为整数。设计程序给出装货方法,使装入背包的货物总价值达到最大。,假设顾客在超市购买各种商品,来到收银台结账,收银员具有面值为100,20,10,5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数,并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。二、 。。,有能力的同学可以完成题目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);printfC请输入背包的负重M:\rT);scanf("%f",&M);printfC请输入各种货物的重量:\n〃);for(i=l;i<=n;i++)scanf(%f〃,&W[i]);printff请输入各种货物的价值:\n〃);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]<value[j+l])t=value[j];value[j]=value[j+l];value[j+l]=t;〃按货物的单位重量价值进行排序q二W[j];W[j]岬[j+1];W[j+1]二q;//相应的货物重量进行排序}}printfC单位价值量(从大到小)如下:\n");for(i=l;i〈=n;i++)printf(,z%]);printf("\n");printff所对应的货物重量如下:\『);for(i=l;i<=n;i++)printfC%",W[i]);printfU\n");i=l;while(M!=0){M-二W[i];//背包负重递减values二values+w[i]*value[i];//计算总价值x[i]二W[i];s二i;s++;if(M<=W[s]){values二values+M*value[s];//如果背包的负重小于货物的重量时,则装货量等于背包的剩奈载重xL++iJ=M;M=0;i++;printf(装货方式如下:\n);for(i=l;i〈=n;i++)printf(,z%"、x[i]);printf ;printf("最大价值为:values=% \n",val