学号
《算法设计与分析》
实验报告三
学生姓名
专业、班级
指导教师
成绩
电子与信息工程系
实验三：贪心算法运用练习
一、实验目的
本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

二、实验步骤与要求
1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；
2．学生独自完成实验指定内容；
3．实验结束后，用统一的实验报告模板编写实验报告。

4．提交说明：
（1）电子版提交说明：
a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验二_学号_姓名”，
如“《算法设计与分析》实验二_09290101_张三”。

b 压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹，
其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验
报告电子版”。

其下分别放置对应实验成果物。

（2）打印版提交说明：
a 不可随意更改模板样式。

b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号
字。

c 行间距：单倍行距。

（3）提交截止时间：2012年12月7日16:00。

三、实验项目
1．传统的找零钱问题的算法及程序实现。

2．特殊的0-1背包问题的求解：本次求解的0-1背包问题的特点为每种物品各有M件，已知每个物品的单位价值，求使得所获价值最大的装包方案。

四、实验过程
找零钱问题:
#include<iostream>
using namespace std;
void Zl(double num)
{
int leave=0;
int a[8];
leave = (int)(num*10)%10;
a[1] = leave/5;
a[0] = (leave%5)/1;
a[7] = num/50;
a[6] = ((int)num%50)/20;
a[5] = (((int)num%50)%20)/10;
a[4] = ((((int)num%50)%20)%10)/5;
a[3] = (((((int)num%50)%20)%10)%5)/2;
a[2] = ((((((int)num%50)%20)%10)%5)%2)/1;
if(a[0]!=0)
cout<<"需要找的0.1元个数为："<<a[0]<<endl;
if(a[1]!=0)
cout<<"需要找的0.5元个数为："<<a[1]<<endl;
if(a[2]!=0)
cout<<"需要找的1元个数为："<<a[2]<<endl;
if(a[3]!=0)
cout<<"需要找的2元个数为："<<a[3]<<endl;
if(a[4]!=0)
cout<<"需要找的5元个数为："<<a[4]<<endl;
if(a[5]!=0)
cout<<"需要找的10元个数为："<<a[5]<<endl;
if(a[6]!=0)
cout<<"需要找的20元个数为："<<a[6]<<endl;
if(a[7]!=0)
cout<<"需要找的50元个数为："<<a[7]<<endl;
}
void main ()
{
double num;
// int
cout<<"请输入你需要找的零钱数："<<endl;
cin>>num;
Zl(num);
cout<<endl;
return;
}
五、实验总结。