算法設(shè)計與分析P3-4

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

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

3、數(shù)j=j-P(T(1),j)* T(1)進行兌換零錢的最佳方案。其次，找零錢問題具有重疊于問題性質(zhì)：a)當(dāng)n=1時，即只能用一種錢幣兌換零錢，錢幣的面值為T0，有 （2） 根據(jù)分析建立正確的遞歸關(guān)系：復(fù)雜度：算法的時間復(fù)雜度主要取決于程序的兩個循環(huán)，所以算法的時間復(fù)雜度為：O(n2)；算法執(zhí)行過程中引入了一個二維數(shù)組，隨著輸入規(guī)模的增大，所需要的空間復(fù)雜度為：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;/硬幣面值數(shù)組T,可以使用的各種面值的硬幣個數(shù)數(shù)組 Coins,n種不同面值的硬幣 int cMAX;/數(shù)組c存放要找的最少硬幣個數(shù) int m; /要找的錢數(shù)m void init() int i; cout<<"輸入硬幣的面值種數(shù)：" cin>>n; cout<<"n輸入硬幣面值及其此面值硬幣的個數(shù)："<<endl; for(i=0;i<n;+i) cin>>Ti>&

5、gt;Coinsi; cout<<"n輸入要找的錢數(shù)：" 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最少硬幣個數(shù)為："<<cm<<endl

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

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

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

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

10、2 9 8 2,在以小面值的硬幣為第一個的情況中，在尋找最優(yōu)組合時，會遇到兩種情況：  a、使用硬幣個數(shù)要比以大面值的硬幣(如9和8)為第一個的情況大得多。  b、尋找到的組合與前面的情況有重復(fù)。 完整程序代碼如下： #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&#