[贪心算法实验报告.docVIP

福建工程学院计算机与信息科学系 实验报告– 2010 学年第 一 学期 任课老师： 王璇 实验题目 设分治算法设计技术的应用 实验时间 实验开始日期：2010/11/02 报告提交日期：2010/11/10 实验目的、要求 （1）实验题目 1．利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。装货方法，使装入背包的货物总价值达到最大面值为、、2）实验设计的数据结构及说明 1.使用的是数组，分别定义商品的价格很商品的质量。 int p[] ={25, 24, 15}; //货物的价值 int w[] ={18, 15, 10}; //货物的重量 2. 使用的是数组，存放各种面值钱币 int a[9]={1000,500,200,100,50,10,5,2,1}; （3）用层次图描述程序结构，并说明程序各函数的名称、功能，图示各函数之间相互的调用关系。 第一题： 第二题：略 （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; in; i++) { r[i] = p[i]/(w[i]*1.0);//求单价 } print(r, n);//打印各物品单价 int remain; int toFill; for(i=0, remain=m; in remain0; i++) { toFill = findMax(r, n); r[toFill] = -1; if((remain - w[toFill]) = 0) { s[toFill] = 1.0; remain = remain - w[toFill]; } else { s[toFill] = (w[toFill] - remain)*1.0 / w[toFill]; remain = 0; } } free(r); return s; } 通过这个函数求出每个商品的单价，并调用void print(double* array, int size)打印出单价的一维double数组。循环调用int findMax(double* array, int size)返回单价最大的商品的下标（将前一个最大值赋值为-1），将商品根据单价由大到小装进背包。最后计算背包中每种商品的比例，并返回值。(可通过更改数组跟宏定义来改变数据) 第二题： int a[9]={1000,500,200,100,50,10,5,2,1};//定义一个存放各种面值钱币的数组 (单位为角） 由用户决定需要转换的金钱的总额 for(int i=0;i9;i++)//由于上面数组有九个值。循环九次 { while(money=a[i])//当钱额小于面值时退出循环 { money=money-a[i];//当前金额减去面值 tmpMoney++;//保存当前面值的张数 } printf(%d元的张数为：%d\n,a[i],tmpMoney); tmpMoney=0;//把这下一次的数量清零 } （5）测试数据的设计及预期结果 第一题： 测试数据为： int p[] ={25, 24, 15}; //货物的价值 int w[] ={18, 15, 10}; //货物的重量 const int N = 3; //货物种类的总数 const int M = 20; //背包的大小 (可通过更改数组跟宏定义来改变数据) 第二题： 测试数据也预期结果相同。 （6）总结及心得体会： 此次实验让我对贪心算法的思想有了初步的了解，并且学会了用贪心算法解决一