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

找零问题贪心算法实现一、 实验描述当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。二、 实验原理具体实例：假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99253，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。具体实现：/找零钱算法/By falcon/输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分/输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案参考实验代码部分。三、 实验代码#ifndef LEASTCOINS_H#define LEASTCOINS_Hclass LeastCoinspublic:LeastCoins();LeastCoins();void run();private:int number; / 不同面值的硬币个数int TotalMoney; / 要找回的总钱数int *T; / 存储硬币的面值int *Coins; / 硬币的个数int *m; / mij 是以 最大面值 i 要找回 钱数是 j 需要硬币数的 最少个数bool input();int changeMoney(int i,int j); / i 是 第 i 中硬币void output();void traceback(); / 寻找 轨迹;#endif#include #include #include #include #define N 10 ifstream inputFile(input.txt,ios: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;iN;i+)mi=new int N*N;LeastCoins:LeastCoins()delete T;delete Coins;for (int i=0;inumber;outputFile有 number 不同的硬币.endl;outputFilesetw(4)面值setw(7)个数endl;int sum=0;for (int i=1;iTi;inputFileCoinsi;outputFilesetw(3)Tisetw(3) setw(3)CoinsiTotalMoney;outputFile需要找回的总钱数为: TotalMoney=TotalMoney)return true;elseoutputFile所有硬币的总钱数是 sum 小于需要找回的总钱数 TotalMoney1) if (jTi) / 要找的钱数 小于 该硬币的面值mi-1j=changeMoney(i-1,j);mij=mi-1j;return mij;elseint X=j/Ti; X=(X(T2+X-1)mij=T2+X-1; else mij=T1+X;return mij;else if(i=1)/ 此时 i=1if (j%T1)=0 & (j/T1=Coins1)m1j=j/T1;return m1j;else return 1000000; else return 1000000;void LeastCoins:output()if (mnumberTotalMoney1000000) / 判断是否 有解outputFile需要最少的硬币个数是: mnumberTotalMoneyendl;outputFilesetw(4)面值setw(7)个数endl;traceback();else outputFile无解=2;i-)int X=j/Ti; / 最多需要面值为 Ti 的硬币的个数X=(XCoinsi ? X : Coinsi) ; / 取 X 和 Coinsi的较小值 int T1=mi-1j-X*Ti+X;int T2=mi-1j-(X-1)*Ti+X-1;if (T1T2)outputFilesetw(3)Tisetw(3) setw(3)Xendl;j-=X*Ti;elseoutputFilesetw(3)Tisetw(3) setw(3)(X-1)endl;j-=(X-1)*Ti;outputFilesetw(3)Tisetw(3) setw(3)(j/T1)endl;int main()LeastCoins LC;LC.