《算法设计与分析》实验三

《算法设计与分析》

实验报告三学生姓名专业、班级指导教师计算机与信息工程学院软件工程系2014年10月20日实验三：贪心算法运用练习一、 实验目的本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。二、 实验步骤与要求实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；学生独自完成实验指定内容；实验结束后，用统一的实验报告模板编写实验报告。提交说明：（1） 电子版提交说明：a需要提交Winrar压缩包，文件名为“《算法设计与分析》实验四_学号_姓名”，如“《算法设计与分析》实验四_09290101_张三”。b压缩包内为一个“《算法设计与分析》实验四_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。（2） 打印版提交说明：a不可随意更改模板样式。b字体：中文为宋体，大小为10号字，英文为TimeNewRoman，大小为10号字。c行间距：单倍行距。（3） 提交截止时间：2014年11月3日16:00。三、 实验项目传统的找零钱问题的算法及程序实现。特殊的0-1背包问题的求解：本次求解的0-1背包问题的特点为每种物品各有M件，已知每个物品的单位价值，求使得所获价值最大的装包方案。四、 实验过程算法实现程序源代码（请写入必要的注释）。#include<iostream>usingnamespacestd;intmain（）（inta[5]={50,20,10,5,1};〃可以用来找零的钱，以元为单位，不考虑角分intmoney;cout<<"请输入找零钱数：”;cin>>money;intb[100];inti=0;intj=0;while(money>0)(if(money>=a[i])(b[j]=a[i];j++;money-=a[i];}elsei++;}cout<<"找回来的零钱："<<'\n';for(intx=0;x<j;x++)cout<<b[x]<<”";cout<<endl;}#include<iostream>usingnamespacestd;voidKANPSACK_DP(intc[50][50],intw[50],intv[50],intn,intC)(for(inti=0;i<=C;i++)(c[0][i]=0;}for(i=1;i<=n;i++)(c[i][0]=0;for(intj=1;j<=C;j++)(if(w[i]<=j)(if(v[i]+c[i-1][j-w[i]]>c[i-1][j])c[i][j]=v[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}elsec[i][j]=c[i-1][j];}}}voidOUTPUT_SACK(intc[50][50],intx[50],intw[50],intn,intC)(for(intk=n;k>=2;k--)(if(c[k][C]==c[k-1][C])x[k]=0;else(x[k]=1;C=C-w[k];}}x[1]=c[1][C]?1:0;}intmain()intc[50][50];intw[50],v[50];intx[50];intC,n;cout<<"输入物品的总个数：”；cin>>n;cout<<"输入背包的总容量：”；cin>>C;cout<<"依次输入物品的重量："<<endl;for(inti=1;i<=n;i++)(cin>>w[i];}cout<<"依次输入物品的价值："<<endl;for(i=1;i<=n;i++)(cin>>v[i];}KANPSACK_DP(c,w,v,n,C);OUTPUT_SACK(c,x,w,n,C);cout<<"最优解为："<<endl;for(i=1;i<=n;i++)(