贪心算法实验报告

1、福建工程学院计算机与信息科学系实验报告 2009 2010 学年第 一 学期 任课老师： 王璇 实验题目设分治算法设计技术的应用实验时间实验开始日期：2010/11/02 报告提交日期：2010/11/10 实验目的、要求（1）实验题目1利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。2设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买

2、商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。（2）实验设计的数据结构及说明1.使用的是数组，分别定义商品的价格很商品的质量。int p =25, 24, 15; /货物的价值int w =18, 15, 10; /货物的重量2. 使用的是数组，存放各种面值钱币int a9=1000,500,200,100,50,10,5,2,1; （3）用层次图描述程序结构，并说明程序各函数的名称、功能，图示各函数之间相互的调用关系。第一题：int main(void)greedySolve(p, w, N, M)贪心算法求比率findMax(r, n)返回最大值的下标print(x

3、, N)打印double型数组调用调用第二题：略（4）各个函数的设计及说明第一题： /贪心算法求解，返回double数组，每一个位对应着相应的货物要装入的比率double* greedySolve(int* p, int* w, int n, int m) double* r = (double*)malloc(sizeof(double)*n);/初始化指针 double* s = (double*)malloc(sizeof(double)*n); int i; for(i=0; i<n; i+) ri = pi/(wi*1.0);/求单价 print(r, n);/打印各物品单价

4、int remain; int toFill; for(i=0, remain=m; i<n && remain>0; i+) toFill = findMax(r, n); rtoFill = -1; if(remain - wtoFill) >= 0) stoFill = 1.0; remain = remain - wtoFill; else stoFill = (wtoFill - remain)*1.0 / wtoFill; remain = 0; free(r); return s;通过这个函数求出每个商品的单价，并调用void print(dou

5、ble* array, int size)打印出单价的一维double数组。循环调用int findMax(double* array, int size)返回单价最大的商品的下标（将前一个最大值赋值为-1），将商品根据单价由大到小装进背包。最后计算背包中每种商品的比例，并返回值。(可通过更改数组跟宏定义来改变数据)第二题：int a9=1000,500,200,100,50,10,5,2,1;/定义一个存放各种面值钱币的数组 (单位为角）由用户决定需要转换的金钱的总额for(int i=0;i<9;i+)/由于上面数组有九个值。循环九次 while(money>=ai)/当钱额小

6、于面值时退出循环 money=money-ai;/当前金额减去面值 tmpMoney+;/保存当前面值的张数 printf("%d元的张数为：%dn",ai,tmpMoney); tmpMoney=0;/把这下一次的数量清零 （5）测试数据的设计及预期结果第一题：测试数据为：int p =25, 24, 15; /货物的价值int w =18, 15, 10; /货物的重量const int N = 3; /货物种类的总数const int M = 20; /背包的大小(可通过更改数组跟宏定义来改变数据)第二题：测试数据也预期结果相同。（6）总结及心得体会：此次实验让我对贪心算法的思想有了初步的了解，并且学会了用贪心算法