最少硬幣問題

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

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

3、思路，可以將所有的硬幣價值都放在一個數(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ù)組中-價值int *coi n = new int n+1;/可以使用的硬幣個數(shù)存放在coin中-個數(shù)c

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