最少硬幣問題.doc

《最少硬幣問題.doc》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、實驗報告學號：姓名：班級：課程名稱算法設計與分析實驗課時2實驗項目最少硬幣問題實驗時間實驗目的設有n種不同面值的硬幣，各硬幣的面值存于數組T[1:n]中?，F要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個數存于數組Coins[1:n]中。對任意錢數0≤m≤20001，設計一個用最少硬幣找錢m的方法。實驗環(huán)境VisualC++實驗內容（算法、程序、步驟和方法）一、算法策略對于給定的1≤n≤10，硬幣面值數組T和可以使用的各種面值的硬幣個數數組Coins，以及錢數m，0≤m≤20001，計算找錢m的最少硬幣數。二、算法設計（步驟）算法思想：（1）動態(tài)規(guī)劃實現長度為m的數組f[1...m

2、]中存放一系列子結果，即f[i]為要湊的錢數為i時，所需的最少硬幣數，則c[m]為所求;當要找的錢數i(1

3、個就是結果。（4）另外一種思路，可以將所有的硬幣價值都放在一個數組，就變成了0-1背包問題，所需考慮的就是放不放的問題。算法步驟：#includeusingnamespacestd;intmin(inta,intb);intmain(){實驗內容（算法、程序、步驟和方法）intn;//n種不同面值的硬幣intm;inti,j,k;cout<<"請輸入有幾種不同的面值:";cin>>n;int*t=newint[n+1];//硬幣的面值存放在t數組中--價值int*coin=newint[n+1];//可以使用的硬幣個數存放在coin中--個數cout<<"請輸入"<

4、>t[i]>>coin[i];cout<<"請輸入要找的錢數m:";cin>>m;intdp[20002]={0};//dp[i]用來記錄錢數為i時的最少的硬幣數for(i=1;i<=m;i++)dp[i]=99999;for(i=1;i<=n;i++)//硬幣面值的種數for(j=1;j<=coin[i];j++)//硬幣的面值的個數for(k=m;k>=t[i];k--){dp[k]=min(dp[k-t[i]]+1,dp[k]);}cout<<"最少需要用到的硬幣個數

5、是:";if(dp[m]==99999)cout<<-1<

6、解包含子問題的最優(yōu)解時，稱該問題有最優(yōu)子結構性質。以自底向上的地從子問題的最優(yōu)解構造出整個問題的最優(yōu)解。指導老師評議成績評定：指導教師簽名：