找零问题贪心算法实现.docx
找零问题贪心算法实现找零问题贪心算法实现 一、 实验描述 当前有面值分别为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_H class LeastCoins public: ; #endif #include <iostream.h> #include <fstream.h> #include <cstdlib> #include <iomanip.h> #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; / 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 LeastCoins:changeMoney(int i,int j) if (i>1) if (j<Ti) / 要找的钱数 小于 该硬币的面值 mi-1j=changeMoney(i-1,j);mij=mi-1j; else return mij; if (input) changeMoney(number,TotalMoney); output; inputFile>>number; outputFile<<"有 "<<number<<" 不同的硬币."<<endl; outputFile<<setw(4)<<"面值"<<setw(7)<<"个数"<<endl; int sum=0; for (int i=1;i<=number;i+) inputFile>>TotalMoney; outputFile<<"需要找回的总钱数为: "<<TotalMoney<<endl; if (T!=NULL && Coins!=NULL) return false; if (sum>=TotalMoney)return true; else outputFile<<"所有硬币的总钱数是 "<<sum<<" 小于需要找回的总钱数 return false; inputFile>>Ti; inputFile>>Coinsi; outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<Coinsi<<endl; sum+=Ti*Coinsi; bool LeastCoins:input delete T; delete Coins; for (int i=0;i<N;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;i<N;i+)mi=new int N*N; "<<TotalMoney<<endl; int 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=1 else return 1000000; if (j%T1)=0 && (j/T1<=Coins1) else return 1000000; m1j=j/T1; return m1j; 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<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<(j/T1)<<endl; 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+X-1; if (T1<T2) outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<X<<endl; j-=X*Ti; else outputFile<<setw(3)<<Ti<<setw(3)<<" "<<setw(3)<<(X-1)<<endl;if (mnumberTotalMoney<1000000) / 判断是否 有解 else outputFile<<"无解"<<endl; outputFile<<"需要最少的硬币个数是: "<<mnumberTotalMoney<<endl; outputFile<<setw(4)<<"面值"<<setw(7)<<"个数"<<endl;traceback; j-=(X-1)*Ti; 四、 运行结果 图1 运行结果 五、 实验总结 对贪心算法不是特别熟悉，以至于在编写程序时遇到好多错误，好在差不多都改正了，此程序尚有不足之处，希望在以后的深入学习后能编写个更好的程序。
