1、問題描述設有n種不同面值的硬幣，各硬幣的面值存于數組T1:n中。現要用這些面值的硬幣來找錢，可以實用的各種面值的硬幣個數不限。（1）當只用硬幣面值T1,T2,Ti時，可找出錢數j的最少硬幣個數記為C(i,j)。若只用這些硬幣面值，找不出錢數j時，記C(i,j)=。 給出C(i,j)的遞歸表達式及其初始條件。其中，1in,1jL.(2)設計一個動態規劃算法，對于1jL，計算出所有的C(n,j).算法只允許使用一個長度為L的數組。用L和n作為變量表示算法的時間復雜性。（3）在C(n,j),1<=j<=L，已計算出的情況下，設計一個貪心算法，對任意錢數m<=L，給出用最少硬幣找錢m

2、的方法。當C（n,m）時，算法的計算時間為O(n+C(n,m)。分析這個問題用動態規劃來解，歸結到動態規劃上面就變成了無限背包問題。區別在于，現在我們需要求一個最少的硬幣數而不是最大值。但是選擇的情況也是相同的，即每次選擇都可以選擇任何一種硬幣。 首先，找零錢問題具有最優子結構性質：兌換零錢問題的最優子結構表述：對于任意需要找的錢數j，一個利用Tn中的n個不同面值錢幣進行兌換零錢的最佳方案為P(T(1),j)，P(T(2),j),.,P(T(n),j)，即此時的最少錢幣個數C(n,j)=k=0nP(T(k),j)則P(T(2),j),.,P(T(n),j)一定是利用Tn中n個不同的面值錢幣對錢

3、數j=j-P(T(1),j)* T(1)進行兌換零錢的最佳方案。其次，找零錢問題具有重疊于問題性質：a)當n=1時，即只能用一種錢幣兌換零錢，錢幣的面值為T0，有 （2） 根據分析建立正確的遞歸關系：復雜度：算法的時間復雜度主要取決于程序的兩個循環，所以算法的時間復雜度為：O(n2)；算法執行過程中引入了一個二維數組，隨著輸入規模的增大，所需要的空間復雜度為：O(n2)算法： #include<iostream> #include<cstring> using namespace std; #define MAX 20002 #define INF 99999

4、99 #define min(a,b) (a)>(b)?(b):(a) int T11,Coins11,n;/硬幣面值數組T,可以使用的各種面值的硬幣個數數組 Coins,n種不同面值的硬幣 int cMAX;/數組c存放要找的最少硬幣個數 int m; /要找的錢數m void init() int i; cout<<"輸入硬幣的面值種數：" cin>>n; cout<<"n輸入硬幣面值及其此面值硬幣的個數："<<endl; for(i=0;i<n;+i) cin>>Ti>&

5、gt;Coinsi; cout<<"n輸入要找的錢數：" cin>>m; int main(int argc, char *argv) init(); for(int i=0;i<=m;+i) ci=INF; c0=0; for(int i=0;i<n;+i) for(int j=1;j<=Coinsi;+j) for(int k=m;k>=Ti;-k) ck=min(ck,ck-Ti+1); if(cm!=INF) cout<<"n最少硬幣個數為："<<cm<<endl

6、; else cout<<"-1"<<endl; return 0; 運行結果：時間復雜度： 從上面算法可知，最優值cj的計算過程中，最外層為循環for(j=1;j<=L;j+)嵌套著while(k>1&&flag=0)循環，而while(k>1&flag=0)循環中又嵌套著三個并列的for循環。因此本算法最壞情況下的復雜度是O(L*2n)；最好的情況當然是里面for循環的條件不滿足而不執行，此時的復雜度為O(L*n)。其中：L表示需要兌換的零錢數，對于L來說，該值一般不是很大，對于錢幣來說，L會小

7、于100元，即10 000分；n表示錢幣的種類，n值一般不會很大如錢幣總的有13種(從1分，2分，100元)。經過以上分析，如是最壞情況時的復雜度應為O(L*2n),則該值對于內存和運行速度較小的自動售貨機等的應用前景則不會很好。但本算法中的遞歸結構在L>Tn時，有可見對于錢幣j=L時，求c(n,j)時，并不要求對從1ij，的所有情況都要求c(n,i)+1，而是只求。其中：1kn。錢幣一般只有13種左右，因此其效率大為上升。最壞的情況下需要執行而M小于100元即10000分，遠大于n。本算法的動態規劃算法的時間復雜性比該問題的一般動態規劃算法的效率要好得多。該算法的時間復雜性是

8、103數量級的對于應用于自動售貨機等運行速度較慢的機器來說是不成問題的。貪心算法由貪心算法可知盡量用大面值的硬幣組合來找錢，可以使使用的硬幣最少。而貪心算法對最少硬幣問題的解決總是可以得到最優解很好的近似解。   例如：9分面值的硬幣5枚，8分面值的硬幣5枚，  2分面值的硬幣8枚，要找25分錢。  設要找的錢為m，硬幣種類為n，ti(0<i<=n)為硬幣的面值，ci為可以使用的各種面值的硬幣個數, ki為第i種面值的硬幣可以使用的最多個數  （ki=minm/ti,ci） 

9、;(1)將硬幣依面值大小排序 9 8 2  (2)按面值種類劃分不同情況 有多少種面值就劃分多少種情況. 每種情況的第一枚硬幣面值各不一樣,其后對剩余的硬幣按面值從大到小排列.  劃分為三個情況：982，892，298。  對應ki為：k0=3, k1=3 ,k2=8  得到近似最優解群為9分1枚,8分2枚;9分1枚,8分1枚,2分4枚;9分1枚,2分8枚. 算法優化 1,在尋找最優組合過程中，有些情況可以不予考慮。比如上例中

10、2 9 8 2,在以小面值的硬幣為第一個的情況中，在尋找最優組合時，會遇到兩種情況：  a、使用硬幣個數要比以大面值的硬幣(如9和8)為第一個的情況大得多。  b、尋找到的組合與前面的情況有重復。 完整程序代碼如下： #include <stdio.h> #include <fstream.h> #include<stdlib.h> int n,money; struct ctype

11、0;  int value;  int coin;  template<class type> void make2Darray(type * * &x,int rows,int cols)   x=new type *rows;  for(int i=0;i<rows;i+)  xi=new type

12、cols;  void swap(ctype &a,ctype &b)   ctype temp; temp=a; a=b; b=temp;  int partition(ctype array,int p,int r)  int i,j; ctype key; i=p; j=r+1; key=arrayp; w

13、hile(true)  while(array+i.value<key.value); while(array-j.value>key.value); if(i>=j) break;  swap(arrayi,arrayj);  arrayp=arrayj; arrayj=key; return j;  void quicksort(ctype array,int p,int r) 

14、60; int q; if(p<r)  q=partition(array,p,r); quicksort(array,p,q-1); quicksort(array,q+1,r);   void main()   ifstream input("input.txt");  ofstream output("output.txt");  input&g

15、t;>n;  int * coins=new intn+1;  ctype * T=new ctypen+1;  for(int i=1;i<=n;i+)   input>>Ti.value;  input>>Ti.coin;   input>>money; quicksort(T,1,n); /*for(i=1;i&l

16、t;=n;i+)  coinsi=Ti.coin; */  int max=0;  for(i=1;i<=n;i+)  max+=Ti.coin;  max+=10;   int * min=new intmoney+1;   min0=0; int * * cnum;  make2Darray(cnum,money+1,n+1);

17、  for(i=0;i<=money;i+)  for(int j=1;j<=n;j+)  cnumij=0; if(T1.value=1) min1=1;cnum11=1; else min1=max;  int j=2;  while(j<=money)   minj=max;  i=1;   while(i<=n)&&(j>=Ti.value)      int coinumber=cnumj-Ti.valuei;  coinumber+;  if(minj>1+minj-Ti.value)&&(coinumber<=Ti.coin)      for(int&#