1、算法設計與分析課程設計一、 課程題目零錢問題貪心算法實現二、課程摘要1）題目描述使用貪心算法設計思想設計算法實現找零錢問題。例題13-4 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。1）在給定錢幣面值的前提下，實現找回盡量少硬幣的輸出方案2）分析算法性能2）貪心算法

2、簡述在求最優解問題的過程中，依據某種貪心標準，從問題的初始狀態出發，直接去求每一步的最優解，通過若干次的貪心選擇，最終得出整個問題的最優解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優解，而由問題自身的特性決定了該題運用貪心算法可以得到最優解。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其它算法相比具有一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實現過程，貪心算法的核心、基本性質、特

3、點及其存在的問題。并通過貪心算法的特點舉例列出了以往研究過的幾個經典問題，對于實際應用中的問題，也希望通過貪心算法的特點來解決。三、課程引言首先，證明找零錢問題的貪婪算法總能產生具有最少硬幣數的零錢。證明：（1）找零錢問題的最優解必以一個貪心選擇開始，當總金額為N,硬幣面值為25，10，5，1時。 設最大容許的硬幣面值為m,最優解必包含一個面值為m的硬幣: 設A是一個最優解，且A中的第i個硬幣面值為f(i)。 當f(1)=m（此處為25）,得證； 若f(1)1)之和1時，若jTn,即第n種錢幣面值比所兌換零錢數小,因此有。當k為時，C(n,j)達到最小值，有P(T(k0),j)=P(T()，j

4、-T()+1若j=Tn，即用n種錢幣兌換零錢，第n種錢幣面值與兌換零錢數j相等，此時有C(n,j)=C(n,Tn)=1；若jTn，即第n種錢幣面值比所兌換零錢數大，因此兌換零錢只需考慮前n-1種錢幣即可，故有C(n,j)=C(n-1,j)，且P(T(n-1),j)=0。從以上討論可知該問題具有重疊子問題性質。（1） 根據分析建立正確的遞歸關系。答： （2） 分析利用你的想法解決該問題可能會有怎樣的時空復雜度。答：算法的時間復雜度主要取決于程序的兩個循環，所以算法的時間復雜度為；算法執行過程中引入了一個二維數組，隨著輸入規模的增大，所需要的空間復雜度為：考慮例1 3 - 4的找零錢問題，假設售貨

5、員只有有限的2 5美分， 1 0美分， 5美分和1美分的硬幣，給出一種找零錢的貪婪算法。這種方法總能找出具有最少硬幣數的零錢嗎？證明結論。源代碼如下：# include using namespace std;const int C=33; const int M=100; /小孩給的錢數const int twentyfnum=3; /25美分硬幣const int tennum=3; /10美分硬幣const int fivenum=3; /5美分硬幣const int onenum=3; /1美分硬幣 const int tnum=twentyfnum+tennum+fivenum+on

6、enum; /硬幣的總數量int main()int atnum,i; /數組初始化,數組中的元素由大到小排列int *p=a;for(i=0;itwentyfnum;i+) *p+=25;for(i=0;itennum;i+) *p+=10;for(i=0;ifivenum;i+) *p+=5;for(i=0;ionenum;i+) *p+=1;bool btnum; q,int n,int c);if(findmoney(a,b,tnum,M-C) int c4=0; /存放應找個各面值硬幣的數量 bool findmoney(int *p,bool *for(i=0;itnum;i+)i

7、f(bi=true)switch(ai)case 25: c0+;break;case 10: c1+;break;case 5: c2+;break;case 1: c3+;break; cout找錢方案:endl; cout25美分:c0枚,10美分:c1枚,5美分:c2枚,1美分:c0枚endl;else cout零錢不夠;system(pause); return 0;bool findmoney(int *p,bool *q,int n,int c) for(int i=0;in;i+) if(pi=c&c!=0) qi=true; c-=pi; if(c=0) break; if(

8、c=0) return true;else return false;在此程序中，程序沒有實現輸入和輸出的模塊，但是具有了找零錢問題的貪心算法解決模塊，所以需要在此程序的基礎上進一步優化，改進后的代碼如下：#include using namespace std; void Zl(double num) int leave=0; double a8; leave = (int)(num*10)%10; a1 = leave/5; a0 = (leave%5)/1; a7 = num/50; a6 = (int)num%50)/20; a5 = (int)num%50)%20)/10; a4 =

9、 (int)num%50)%20)%10)/5; a3 = (int)num%50)%20)%10)%5)/2; a2 = (int)num%50)%20)%10)%5)%2)/1; if(a0!=0) cout需要找的0.1元個數為：a0endl; if(a1!=0) cout需要找的0.5元個數為：a1endl; if(a2!=0) cout需要找的1元個數為：a2endl; if(a3!=0) cout需要找的2元個數為：a3endl; if(a4!=0) cout需要找的5元個數為：a4endl; if(a5!=0) cout需要找的10元個數為：a5endl; if(a6!=0) c

10、out需要找的20元個數為：a6endl; if(a7!=0) cout需要找的50元個數為：a7endl; int main() double num; cout請輸入你需要找的零錢數：num; Zl(num); coutendl; return 0;2）實驗結果比較上一步驟中兩個源代碼運行結果分別如下：第一個的運行結果第二個運行結果比較上面兩個算法，第二個算法在第一個的基礎上增加了輸入輸出功能，方便得到任意數值零錢問題的最優解。五、結論與展望（1）算法實現的復雜度在問題規模很大時可以接受嗎？答：可以接受，因為貪心算法有很好的效率，所以當問題復雜度很大時，就不會對算法的運行時間有太大的影響，

11、可以控制在用戶可以接受的范圍內。（2）如果不用貪心算法方法還能想到其他的解決方式嗎？和貪心算法相比會有更好的效率嗎？答：對于找硬幣問題，有時候動態規劃也能解決，前面也有敘述，動態規劃求解要比貪心算法求解有效率，所以采用動態規劃方法也是一個很好的選擇。（3）所選用的數據結構合適嗎？答：采用了數組的數據結構，合適，因為該數據結構能夠支持對于數組中的元素的隨機訪問，而且方便查詢。（4）該算法都存在哪幾類可能出現的情況，你的測試完全覆蓋了你所想到的這些情況嗎，測試結果如何？答：基本上覆蓋了所有可能的測試結果，但不排除結果出現錯誤的可能。（5）通過實驗對貪心算法的理解及總結*貪心算法的特點從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程，后面的每一步都是當前看