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

《找零问题贪心算法实现.docx》由会员分享，可在线阅读，更多相关《找零问题贪心算法实现.docx（5页珍藏版）》请在三一办公上搜索。

1、找零问题贪心算法实现找零问题贪心算法实现 一、 实验描述 当前有面值分别为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为需要找的钱数，单位全部为分

2、 /输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案 参考实验代码部分。 三、 实验代码 #ifndef LEASTCOINS_H #define LEASTCOINS_H class LeastCoins public: ; #endif #include #include #include #include #define N 10 ifstream inputFile(input.txt,ios:out); ofstream outputFile(output.txt,ios:out); LeastCoins; LeastCoins; void run; int

3、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; / 寻找 轨迹 private: LeastCoins:LeastCoins LeastCoins:LeastCoins void LeastCoins:run int

4、LeastCoins:changeMoney(int i,int j) if (i1) if (jnumber; outputFile有 number 不同的硬币.endl; outputFilesetw(4)面值setw(7)个数endl; int sum=0; for (int i=1;iTotalMoney; outputFile需要找回的总钱数为: TotalMoney=TotalMoney)return true; else outputFile所有硬币的总钱数是 sumTi; inputFileCoinsi; outputFilesetw(3)Tisetw(3) setw(3)Co

5、insiendl; sum+=Ti*Coinsi; bool LeastCoins:input delete T; delete Coins; for (int i=0;iN;i+) delete mi; delete m; 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; TotalMoneyendl; int X=j/Ti; X=(X(T2+X-1) mij=T2+X-1; else mij=T1+X; return mij; else

6、 if(i=1)/ 此时 i=1 else return 1000000; if (j%T1)=0 & (j/T1=2;i-) outputFilesetw(3)Tisetw(3) setw(3)(j/T1)endl; 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; else

7、 outputFilesetw(3)Tisetw(3) setw(3)(X-1)endl;if (mnumberTotalMoney1000000) / 判断是否 有解 else outputFile无解endl; outputFile需要最少的硬币个数是: mnumberTotalMoneyendl; outputFilesetw(4)面值setw(7)个数endl;traceback; j-=(X-1)*Ti; 四、 运行结果 图1 运行结果 五、 实验总结 对贪心算法不是特别熟悉，以至于在编写程序时遇到好多错误，好在差不多都改正了，此程序尚有不足之处，希望在以后的深入学习后能编写个更好的程序。