找零问题贪心算法实现
找零问题贪心算法实现
一、 实验描述
当前有面值分别为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分。 具体实现：
//找零钱算法
//By falcon
//输入：数组m ，依次存放从大到小排列的面值数，n 为需要找的钱数，单位全部为分 //输出：数组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 number; // 不同面值的硬币个数 int TotalMoney; // 要找回的总钱数 int *T; // 存储硬币的面值 int *Coins; // 硬币的个数 int **m; // m[i][j] 是以 最大面值 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 LeastCoins::changeMoney(int i,int j)
{
if (i>1) { if (j>number; outputFile>TotalMoney; outputFile=TotalMoney)return true; else outputFile>T[i]; inputFile>>Coins[i]; outputFile
} } } X=(X(T2+X-1)) m[i][j]=T2+X-1; else m[i][j]=T1+X; return m[i][j]; else if(i==1)// 此时 i==1 { } else return 1000000; if ((j%T[1])==0 && (j/T[1]
void LeastCoins::output()
{
}
void LeastCoins::traceback()
{
}
int main()
{
LeastCoins LC; LC.run(); return 0; int j=TotalMoney; for (int i=number;i>=2;i--) { } outputFile
四、 运行结果
图1 运行结果
五、 实验总结
对贪心算法不是特别熟悉，以至于在编写程序时遇到好多错误，好在差不多都改正了，此程序尚有不足之处，希望在以后的深入学习后能编写个更好的程序。