最少硬幣問題

1、實(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)康脑O(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組 T1:n中。 現(xiàn)要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個(gè)數(shù)存 于數(shù)組Coins1: n中。對任意錢數(shù)OW m<20001,設(shè)計(jì)一個(gè)用最少硬幣找錢 m的方法。實(shí)驗(yàn)環(huán)境Visual C+實(shí)驗(yàn)內(nèi)容(算法、程 序、步驟和 方法)一、算法策略對于給定的1W n< 10,硬幣面值數(shù)組T和可以使用的各種面值 的硬幣個(gè)數(shù)數(shù)組Coins，以及錢數(shù)m 0W mW20001，計(jì)算找錢m的最 少硬幣數(shù)。二、算法設(shè)計(jì)(步驟)算法思想：(1) 動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)長度

2、為m的數(shù)組f1.m中存放一系列子結(jié)果，即fi為要 湊的錢數(shù)為i時(shí)，所需的最少硬幣數(shù)，則cm為所求；當(dāng)要找的 錢數(shù)i(1<ivm)與當(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背包問題，所需考慮的就是放不放的問題。算法步驟：#in clude<iostream>using n amespace std;int min (i nt a,i nt b);int mai n()int n; Un種不同面值的硬幣int m;int i , j ,k;coutvv"請輸入有幾種不同的面值："；cin>>n;int *t = new in t n+1;/硬幣的面值存放在t數(shù)組中-價(jià)值int *coi n = new int n+1;/可以使用的硬幣個(gè)數(shù)存放在coin中-個(gè)數(shù)c

4、outvv"請輸入"vv*v"組硬幣的面值和對應(yīng)的個(gè)數(shù)(中間 用空格隔開):"<<e ndl;for(i = 1 ;i<n+1;i+)cin> >ti>>co in i;coutvv"請輸入要找的錢數(shù)m:"cin>>m;int dp20002=0 ; /dpi用來記錄錢數(shù)為i時(shí)的最少的硬幣數(shù)實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法）for(i=1;i<=m;i+)dpi = 99999;for(i = 1 ;i <= n ; i+) /硬幣面值的種數(shù)for(j = 1 ; j

5、<= coi ni ; j+) /硬幣的面值的個(gè)數(shù)for( k = m ; k >= ti ; k-)dpk = mi n(dpk-ti +1,dpk);coutvv"最少需要用到的硬幣個(gè)數(shù)是:"if(dpm = 99999)coutvv-1vve ndl;else coutvvdpmvv" 個(gè)"vve ndl;int min (i nt a,i nt b)retur n avb?a:b;、復(fù)雜度分析時(shí)間復(fù)雜度：O(nL)空間復(fù)雜度：0( L)'7:沆盧!特它漳;去虧.蘭忌工撫爭Mzr.Cc n Cnsngir才：帛F謹(jǐn)立叱W匚飛.D£兒Ji訃呂尹hEi嘗默罄黠鼎溥幕卷的個(gè)數(shù)(中間用空格隔開八ISm 植是=& 個(gè)Press any key to continue_數(shù)據(jù)記錄和計(jì)算結(jié)論(結(jié)果)用動(dòng)態(tài)規(guī)劃法能夠很好地解決最少銀幣問題，時(shí)間復(fù)雜度為 0( n L),空間復(fù)雜度為0( L)。其中計(jì)算遞歸的表達(dá)式為： cij=mi nci-1j,1+cij-Ti小結(jié)實(shí)驗(yàn)心得：通過這次實(shí)驗(yàn)，是我對 0-1背包問題和動(dòng)態(tài)規(guī)劃法有了 更深的理解。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法第一步就是