找零問題貪心算法實(shí)現(xiàn)知識分享

1、找零問題貪心算法實(shí)現(xiàn)精品文檔找零問題貪心算法實(shí)現(xiàn)一、實(shí)驗描述當(dāng)前有面值分別為2 角 5 分， 1 角， 5 分， 1 分的硬幣，請給出找n 分錢的最佳方案（要求找出的硬幣數(shù)目最少）。二、實(shí)驗原理具體實(shí)例：假如老板要找給我99 分錢，他有上面的面值分別為25，10， 5， 1 的硬幣數(shù)，為了找給我最少的硬幣數(shù)，那么他是不是該這樣找呢，先看看該找多少個25 分的， 99 253，好像是 3 個，要是 4 個的話，我們還得再給老板一個1分的，我不干，那么老板只能給我3 個 25 分的拉，由于還少給我24，所以還得給我 2個 10分的和 4個1分。具體實(shí)現(xiàn)：/找零錢算法/By falcon/輸入：數(shù)組

2、 m，依次存放從大到小排列的面值數(shù)，n 為需要找的錢數(shù)，單位全部為分/輸出：數(shù)組 num，對照數(shù)組 m 中的面值存放不同面值的硬幣的個數(shù)，就找錢方案參考實(shí)驗代碼部分。三、實(shí)驗代碼#ifndef LEASTCOINS_H#define LEASTCOINS_Hclass LeastCoinspublic:LeastCoins();收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔LeastCoins();void run();private:int number; /不同面值的硬幣個數(shù)int TotalMoney; /要找回的總錢數(shù)int *T; /存儲硬幣的面值int *Coins; /硬幣的個數(shù)i

3、nt *m; / mij是以 最大面值 i 要找回錢數(shù)是 j 需要硬幣數(shù)的最少個數(shù)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)<<" 個數(shù) "<<endl; int sum=0;收集于網(wǎng)絡(luò)，如

6、有侵權(quán)請聯(lián)系管理員刪除精品文檔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<<" 需要找回的總錢數(shù)為: "<<Total

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

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<<" 需要最少的硬幣個數(shù)是 : "<<mnumberTotalMoney<<endl; outputFile<<setw(4)<<" 面值 "<<setw(7)<<"

10、 個數(shù) "<<endl;traceback();else outputFile<<"無解 "<<endl;收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔void LeastCoins:traceback()int j=TotalMoney;for (int i=number;i>=2;i-)int X=j/Ti; /最多需要面值為Ti 的硬幣的個數(shù)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)&