找零問題貪心算法實現(xiàn)一、 實驗描述當(dāng)前有面值分別為2角5分，1角，5分，1分的硬幣，請給出找n分錢的最佳方案（要求找出的硬幣數(shù)目最少）。二、 實驗原理具體實例：假如老板要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數(shù)，為了找給我最少的硬幣數(shù)，那么他是不是該這樣找呢，先看看該找多少個25分的， 99253，好像是3個，要是4個的話，我們還得再給老板一個1分的，我不干，那么老板只能給我3個25分的拉，由于還少給我24，所以還得給我2個10分的和4個1分。具體實現(xiàn)：/找零錢算法/By falcon/輸入：數(shù)組m，依次存放從大到小排列的面值數(shù)，n為需要找的錢數(shù)，單位全部為分/輸出：數(shù)組num，對照數(shù)組m中的面值存放不同面值的硬幣的個數(shù)，就找錢方案參考實驗代碼部分。三、 實驗代碼#ifndef LEASTCOINS_H#define LEASTCOINS_Hclass LeastCoinspublic:LeastCoins();LeastCoins();void run();private:int number; / 不同面值的硬幣個數(shù)int TotalMoney; / 要找回的總錢數(shù)int *T; / 存儲硬幣的面值int *Coins; / 硬幣的個數(shù)int *m; / mij 是以 最大面值 i 要找回 錢數(shù)是 j 需要硬幣數(shù)的 最少個數(shù)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)個數(shù)endl;int sum=0;for (int i=1;iTi;inputFileCoinsi;outputFilesetw(3)Tisetw(3) setw(3)CoinsiTotalMoney;outputFile需要找回的總錢數(shù)為: TotalMoney=TotalMoney)return true;elseoutputFile所有硬幣的總錢數(shù)是 sum 小于需要找回的總錢數(shù) TotalMoney1) if (jTi) / 要找的錢數(shù) 小于 該硬幣的面值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需要最少的硬幣個數(shù)是: mnumberTotalMoneyendl;outputFilesetw(4)面值setw(7)個數(shù)endl;traceback();else outputFile無解=2;i-)int X=j/Ti; / 最多需要面值為 Ti 的硬幣的個數(shù)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.