找零问题贪心算法实现知识分享

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

2、 m，依次存放从大到小排列的面值数，n 为需要找的钱数，单位全部为分/输出：数组 num，对照数组 m 中的面值存放不同面值的硬币的个数，就找钱方案参考实验代码部分。三、实验代码#ifndef LEASTCOINS_H#define LEASTCOINS_Hclass LeastCoinspublic:LeastCoins();收集于网络，如有侵权请联系管理员删除精品文档LeastCoins();void run();private:int number; /不同面值的硬币个数int TotalMoney; /要找回的总钱数int *T; /存储硬币的面值int *Coins; /硬币的个数i

3、nt *m; / mij是以 最大面值 i 要找回钱数是 j 需要硬币数的最少个数bool input();int changeMoney(int i,int j); / i是 第 i 中硬币void output();void traceback(); /寻找 轨迹;#endif#include <iostream.h>#include <fstream.h>#include <cstdlib>#include <iomanip.h>#define N 10ifstream inputFile("input.txt",ios

4、:out);ofstream outputFile("output.txt",ios:out);LeastCoins:LeastCoins()number=0;TotalMoney=0;T=new int N;Coins=new int N;m=new int *N;for (int i=0;i<N;i+)mi=new int N*N;LeastCoins:LeastCoins()delete T;delete Coins;for (int i=0;i<N;i+)delete mi;delete m;void LeastCoins:run() if (input

5、() changeMoney(number,TotalMoney); output(); bool LeastCoins:input()inputFile>>number;outputFile<<" 有 "<<number<<" 不同的硬币 ."<<endl; outputFile<<setw(4)<<" 面值 "<<setw(7)<<" 个数 "<<endl; int sum=0;收集于网络，如

6、有侵权请联系管理员删除精品文档for (int i=1;i<=number;i+)inputFile>>Ti; inputFile>>Coinsi;outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<Coinsi<<endl;sum+=Ti*Coinsi;inputFile>>TotalMoney;outputFile<<" 需要找回的总钱数为: "<<Total

7、Money<<endl;if (T!=NULL && Coins!=NULL)if (sum>=TotalMoney)return true;elseoutputFile<<" 所有硬币的总钱数是"<<sum<<"小于需要找回的总钱数"<<TotalMoney<<endl;return false;return false;int LeastCoins:changeMoney(int i,int j)if (i>1) if (j<Ti) /要找的钱数

8、小于 该硬币的面值mi-1j=changeMoney(i-1,j);mij=mi-1j;return mij;elseint X=j/Ti;X=(X<Coinsi ? X : Coinsi) ;int T1=changeMoney(i-1,j-X*Ti);int T2=changeMoney(i-1,j-(X-1)*Ti);mi-1j-X*Ti=T1;mi-1j-(X-1)*Ti=T2;if (T1+X)>(T2+X-1)mij=T2+X-1;else mij=T1+X;return mij;else if(i=1)/此时 i=1if (j%T1)=0 && (j/

9、T1<=Coins1)m1j=j/T1;return m1j;else return 1000000;else return 1000000;void LeastCoins:output()if (mnumberTotalMoney<1000000) /判断是否有解outputFile<<" 需要最少的硬币个数是 : "<<mnumberTotalMoney<<endl; outputFile<<setw(4)<<" 面值 "<<setw(7)<<"

10、 个数 "<<endl;traceback();else outputFile<<"无解 "<<endl;收集于网络，如有侵权请联系管理员删除精品文档void LeastCoins:traceback()int j=TotalMoney;for (int i=number;i>=2;i-)int X=j/Ti; /最多需要面值为Ti 的硬币的个数X=(X<Coinsi ? X : Coinsi) ; /取 X 和 Coinsi 的较小值int T1=mi-1j-X*Ti+X;int T2=mi-1j-(X-1)*Ti

11、+X-1;if (T1<T2)outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<X<<endl; j-=X*Ti;elseoutputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<(X-1)<<endl;j-=(X-1)*Ti;outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)&