找零问题贪心算法实现.doc

《找零问题贪心算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、找零问题贪心算法实现一、实验描述当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。二、实验原理具体实例：假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。具体实现：//找零钱算法//Byfalcon//输入：数

2、组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案参考实验代码部分。三、实验代码#ifndefLEASTCOINS_H#defineLEASTCOINS_HclassLeastCoins{public:LeastCoins();~LeastCoins();voidrun();private:intnumber;//不同面值的硬币个数intTotalMoney;//要找回的总钱数int*T;//存储硬币的面值int*Coins;/

3、/硬币的个数int**m;//m[i][j]是以最大面值i要找回钱数是j需要硬币数的最少个数boolinput();intchangeMoney(inti,intj);//i是第i中硬币voidoutput();voidtraceback();//寻找轨迹};#endif#include#include#include#include#defineN10ifstreaminputFile("input.txt",ios::out);o

4、fstreamoutputFile("output.txt",ios::out);LeastCoins::LeastCoins(){number=0;TotalMoney=0;T=newint[N];Coins=newint[N];m=newint*[N];for(inti=0;i

5、dLeastCoins::run(){if(input()){changeMoney(number,TotalMoney);output();}}boolLeastCoins::input(){inputFile>>number;outputFile<<"有"<>T[i];inputFile

6、>>Coins[i];outputFile<>TotalMoney;outputFile<<"需要找回的总钱数为:"<=TotalMoney)returntrue;elseoutputFile<<"所有硬币的总钱数是"<

7、1){if(j

8、ngeMoney(i-1,j-(X-1)*T[i]);m[i-1][j-X*T[i]]=T1;m[i-1][j-(X-1)*T[i]]=T2;if((T1+X)>(T2+X-1))m[i][j]=T2+X-1;elsem[i][j]=T1+X;returnm[i][j];}}elseif(i==1)//此时i==1{if((j%T