最少硬幣問題.doc

《最少硬幣問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、劃實現(xiàn)長度為m的數(shù)組f[1...m]中存放一系列子結(jié)果，即f[i]為要湊的錢數(shù)為i時，所需的最少硬幣數(shù)，則c[m]為所求;當(dāng)要找的錢數(shù)i(1

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

4、oin=newint[n+1];//可以使用的硬幣個數(shù)存放在coin中--個數(shù)cout<<"請輸入"<>t[i]>>coin[i];cout<<"請輸入要找的錢數(shù)m:";cin>>m;intdp[20002]={0};//dp[i]用來記錄錢數(shù)為i時的最少的硬幣數(shù)for(i=1;i<=m;i++)dp[i]=99999;for(i=1;i<=n;i++)//硬幣面值的種數(shù)for(j=1;j<=coin[i];j++)//硬幣的面值的個數(shù)fo

5、r(k=m;k>=t[i];k--){dp[k]=min(dp[k-t[i]]+1,dp[k]);}cout<<"最少需要用到的硬幣個數(shù)是:";if(dp[m]==99999)cout<<-1<

6、j],1+c[i][j-T[i]]}。小結(jié)實驗心得：通過這次實驗，是我對0-1背包問題和動態(tài)規(guī)劃法有了更深的理解。設(shè)計動態(tài)規(guī)劃法第一步就是要刻畫好最優(yōu)子結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含子問題的最優(yōu)解時，稱該問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。以自底向上的地從子問題的最優(yōu)解構(gòu)造出整個問題的最優(yōu)解。指導(dǎo)老師評議成績評定：指導(dǎo)教師簽名：