贪心算法-找零问题-实验报告

实验三课程名称：算法设计与实现实验名称：贪心算法-找零问题实验日期：2019年5月2日仪器编号：007班级：数媒0000班姓名：郝仁学号0000000000实验内容假设零钱系统的币值是{1，p,p^2,……，p^n},p1,且每个钱币的重量都等于1，设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少，说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度。实验分析引理1（离散数学其及应用3.1.4）：若n是正整数，则用25美分、10美分、5美分和1美分等尽可能少的硬币找出的n美分零钱中，至多有2个10美分、至多有1个5美分、至多有4个1美分硬币，而不能有2个10美分和1个5美分硬币。用10美分、5美分和1美分硬币找出的零钱不能超过24美分。证明如果有超过规定数目的各种类型的硬币，就可以用等值的数目更少的硬币来替换。注意，如果有3个10美分硬币，就可以换成1个25美分和1个5美分硬币；如果有2个5美分硬币，就可以换成1个10美分硬币；如果有5个1美分硬币，就可以换成1个5美分硬币；如果有2个10美分和1个5美分硬币，就可以换成1个25美分硬币。由于至多可以有2个10美分、1个5美分和4个1美分硬币，而不能有2个10美分和1个5美分硬币，所以当用尽可能少的硬币找n美分零钱时，24美分就是用10美分、5美分和1美分硬币能找出的最大值。假设存在正整数n，使得有办法将25美分、10美分、5美分和1美分硬币用少于贪心算法所求出的硬币去找n美分零钱。首先注意，在这种找n美分零钱的最优方式中使用25美分硬币的个数q′，一定等于贪心算法所用25美分硬币的个数。为说明这一点，注意贪心算法使用尽可能多的25美分硬币，所以q′≤q。但是q′也不能小于q。假如q′小于q，需要在这种最优方式中用10美分、5美分和1美分硬币至少找出25美分零钱。而根据引理1，这是不可能的。由于在找零钱的这两种方式中一定有同样多的25美分硬币，所以在这两种方式中10美分、5美分和1美分硬币的总值一定相等，并且这些硬币的总值不超过24美分。10美分硬币的个数一定相等，因为贪心算法使用尽可能多的10美分硬币。而根据引理1，当使用尽可能少的硬币找零钱时，至多使用1个5分硬币和4个1分硬币，所以在找零钱的最优方式中也使用尽可能多的10美分硬币。类似地，5美分硬币的个数相等；最终，1美分的个数相等。同上，由于1+p1+p2+p3+...pk-1=pk-1pk,故当n大于pk时，可以分解为pk与n-pk的值，其中pk只用一个硬币值为pk的硬币就能得到最少硬币数，而子问题变成n-pk的最少硬币数，依次类推，贪心算法总能得到最好的结果。假若最优解不含币值jp的钱币，即112210jjpxpxpxxy那么存在1,1,0,jipxi，，如果不是，则11)(1(12112210jjjjppppppxpxpxxy与jpy矛盾，不妨设pxi，那么用1个币值为1ip的钱币替换p个币值为jp的钱币，总钱币数将减少1p，与这个解为最优解矛盾。下面证明最优解签好含有jp/y个币值jp的钱币。设钱数为y时最优解是yFj，则jjjjjjpyyFpypyFyF11设jjptpy其中jpyt/通过对t的归纳不难证明1jjFtyF，即最优解中含有jpy/个币值jp的钱币。上诉算法在最坏情况下的时间复杂度是}log,min{ynOnW.实验源代码//找零ConsoleApplication1.cpp:此文件包含main函数。程序执行将在此处开始并结束。//数媒1703班-1191170329-唐思成//coin.cpp:定义控制台应用程序的入口点。//#includepch.h#includeiostream#includemath.husingnamespacestd;//money需要找零的钱//coin可用的硬币的种类//n硬币种类的数量voidZhaoLing(intmoney,int*coin,intn){int*coinNum=newint[money+1]();//存储1...money找零最少需要的硬币的个数int*coinValue=newint[money+1]();//最后加入的硬币，方便后面输出是哪几个硬币coinNum[0]=0;for(inti=1;i=money;i++){intminNum=i;//i面值钱，需要最少硬币个数intusedMoney=0;//这次找零，在原来的基础上需要的硬币for(intj=0;jn;j++){if(i=coin[j])//找零的钱大于这个硬币的面值{if(coinNum[i-coin[j]]+1=minNum&&(i==coin[j]||coinValue[i-coin[j]]!=0))//所需硬币个数减少了{minNum=coinNum[i-coin[j]]+1;//更新usedMoney=coin[j];//更新}}}coinNum[i]=minNum;coinValue[i]=usedMoney;}//输出结果if(coinValue[money]==0)cout找不开零钱endl;else{cout需要最少硬币个数为：coinNum[money]endl;cout硬币分别为:;while(money0){coutcoinValue[money],;money-=coinValue[money];}coutendl;}delete[]coinNum;delete[]coinValue;}intmain(){intMoney;intn,i,p;cout请输入需要找零的钱的值endl;cinMoney;cout请输入硬币种类的数量endl;cinn;int*coin=(int*)malloc(n*sizeof(int));//定义动态长度的数组cout请输入零钱的底数endl;while(1){cinp;if(p0){break;}else{cout输入的数小于零，请重新输入endl;}}for(i=0;in;i++){coin[i]=pow(p,i);}cout找零系统中的零钱种类为：endl;for(i=0;in;i++){coutcoin[i],;}coutendl;ZhaoLing(Money,coin,n);system(pause);return0;}实验结果