最少硬幣問題(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)報(bào)告學(xué)號(hào)： 姓名： 班級(jí)：課程名稱算法設(shè)計(jì)與分析實(shí)驗(yàn)課時(shí)2實(shí)驗(yàn)項(xiàng)目最少硬幣問題實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)?zāi)康?設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T1:n中。現(xiàn)要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個(gè)數(shù)存于數(shù)組Coins1:n中。 對(duì)任意錢數(shù)0m20001，設(shè)計(jì)一個(gè)用最少硬幣找錢m的方法。實(shí)驗(yàn)環(huán)境Visual C+實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法）1、 算法策略對(duì)于給定的1n10，硬幣面值數(shù)組T和可以使用的各種面值的硬幣個(gè)數(shù)數(shù)組Coins，以及錢數(shù)m，0m20001，計(jì)算找錢m的最少硬幣數(shù)。2、 算法設(shè)計(jì)（步驟）算法思想：（1）動(dòng)態(tài)規(guī)劃實(shí)現(xiàn) 長度為m的數(shù)組f

2、1.m中存放一系列子結(jié)果，即fi為要湊的錢數(shù)為i時(shí) ，所需的最少硬幣數(shù)，則cm為所求; 當(dāng)要找的錢數(shù)i(1<i<m)與當(dāng)前所試探的硬幣面值k相等時(shí)，結(jié)果為1，即ci=1 ；當(dāng)i大于當(dāng)前所試探硬幣面值k時(shí)，若fi為0，即還未賦過值，且ci-k不為0，即從i元錢中刨去k元后剩下的錢數(shù)可以找開，則ci=ci-k+1，若fi不為0，即已賦過值，則fi為fi-k+1和fi中較小的。 （2）硬幣問題就是一個(gè)多重背包問題。 （3）動(dòng)態(tài)遷移方程為 dpk = mindpk-ti+1,dpk 將第i個(gè)硬幣拿出去得到的一個(gè)最少的找硬幣數(shù)+1，和原硬幣數(shù)相比最小的那個(gè)就是結(jié)果。 （4） 另外一種思路，可

3、以將所有的硬幣價(jià)值都放在一個(gè)數(shù)組，就變成了0-1背包問題，所需考慮的就是放不放的問題。 算法步驟：#include<iostream> using namespace std; int min(int a,int b); int main() 實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法） int n; /n種不同面值的硬幣 int m; int i , j ,k; cout<<"請(qǐng)輸入有幾種不同的面值:" cin>>n; int *t =new intn+1; /硬幣的面值存 放在t數(shù)組中 - 價(jià)值 int *coin = new int n+1;

4、 /可以使用的硬幣個(gè)數(shù)存放在coin中-個(gè)數(shù) cout<<"請(qǐng)輸入"<<n<<"組硬幣的面值和對(duì)應(yīng)的個(gè)數(shù)（中間用空格隔開）:"<<endl; for(i = 1 ;i<n+1;i+) cin>>ti>>coini; cout<<"請(qǐng)輸入要找的錢數(shù)m:" cin>>m; int dp20002=0 ; /dpi 用來記錄錢數(shù)為i時(shí)的最少的硬幣數(shù) for(i=1;i<=m;i+) dpi = 99999; for(i = 1 ;i

5、<= n ; i+) /硬幣面值的種數(shù) for(j = 1 ; j <= coini ; j+) /硬幣的面值的個(gè)數(shù) for( k = m ; k >= ti ; k- ) dpk = min(dpk-ti +1,dpk); cout<<"最少需要用到的硬幣個(gè)數(shù)是:" if(dpm = 99999)cout<<-1<<endl; else cout<<dpm<<"個(gè)"<<endl; int min(int a,int b) return a<b?a:b; 三、復(fù)雜度分析 時(shí)間復(fù)雜度：O（nL） 空間復(fù)雜度：O（L）數(shù)據(jù)記錄和計(jì)算結(jié) 論（結(jié) 果）用動(dòng)態(tài)規(guī)劃法能夠很好地解決最少銀幣問題，時(shí)間復(fù)雜度為O（nL），空間復(fù)雜度為O（L）。其中計(jì)算遞歸的表達(dá)式為：cij=minci-1j,1+cij-Ti。小結(jié)實(shí)驗(yàn)心得：通過這次實(shí)驗(yàn)，是我對(duì)0-1背包問題和動(dòng)態(tài)規(guī)劃法有了更深的理解。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法第一步就是要刻畫好最優(yōu)子結(jié)構(gòu)