1、專業(yè)課程實驗報告課程名稱：算法分析與設(shè)計開課學(xué)期：2014 至 2015 學(xué)年第1 學(xué)期專業(yè)：軟件工程年級班級：2012級03班學(xué)生姓名：李明洋 學(xué)號：222012321062053實驗教師：曹嚴元計算機與信息科學(xué)學(xué)院軟件學(xué)院實驗項目名稱 貪心算法實驗時間 2014年11月14 實驗類型驗證性口設(shè)計性綜合性 日|一、實驗?zāi)康恼莆肇澬姆ǖ幕舅枷敕椒?；了解適用于用貪心法求解的問題類型，并能設(shè)計相應(yīng)貪心法算法；掌握貪心算法復(fù)雜性分析方法分析問題復(fù)雜性。二、實驗要求預(yù)習(xí)實驗指導(dǎo)書及教材的有關(guān)內(nèi)容，掌握貪心算法的基本思想；嚴格按照實驗內(nèi)容進行實驗，培養(yǎng)良好的算法設(shè)計和編程的習(xí)慣；認真聽講，服從安排，獨

2、立思考并完成實驗。三、實驗內(nèi)容與設(shè)計（主要內(nèi)容，操作步驟、算法描述或程序代碼）實現(xiàn)背包問題的貪心算法procedure KNAPSACK(P, W, M, X, n) /P(1： n)和W(1； n)分別含有按P(i)/W3P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1： n)是解向量 real P(1： n)， W(1： n)， X(1： n)， M，cu； integer i， n；X-0 /將解向量初始化為零 cuM /cu是背包剩余容量 for i 1 to n doif W(i)cu then exit endifX(i) 1 cucu-W(i

3、) repeat if iWn then X(i) cu/ W(i) endifend GREEDY-KNAPSACKprocedure prim(G,)status“unseen” / T 為空 status1“tree node” / 將 1 放入 T for each edge(1,w) dostatusw“fringe” / 找到 T 的鄰接點 dadw 1; /w通過1與T建立聯(lián)系 distw weight(1,w) /w至U T 的距離 repeatwhile statust尹 “tree node” dopick a fringe u with min distw / 選取到U

4、T 最近的節(jié)點 statusu“tree node” for each edge(u,w) do修改w和T的關(guān)系repeat repeat程序代碼：#include struct goodinfofloat p; /物品效益float w; /物品重量float X; /物品該放的數(shù)量int flag; /物品編號;/物品信息結(jié)構(gòu)體void Insertionsort(goodinfo goods,int n)int j,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益，重量比值做升序排列void bag(goodinf

5、o goods,float M,int n)float cu;int i,j;for(i=1;i=n;i+)goodsi.X=0;cu=M; /背包剩余容量for(i=1;icu)/當該物品重量大與剩余容量跳出break;goodsi.X=1;cu=cu-goodsi.w;/確定背包新的剩余容量if(i=n)goodsi.X=cu/goodsi.w;/該物品所要放的量 for(j=2;j=n;j+) goods0=goodsj;i=j-1;while (goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout最優(yōu)解為：endl

6、;for(i=1;i=n;i+)cout第i件物品要放:；coutgoodsi.Xendl;void main()cout|運用貪心法解背包問題|endl;cout|endl; int j;int n;float M;goodinfo *goods;/定義一個指針while(j)coutn;goods=new struct goodinfo n+1;/coutM;coutendl;int i;for(i=1;i=n;i+) goodsi.flag=i;cout請輸入第igoodsi.w;F八算法賣驗、貪心法DebugKnapsack. exe*運用貪心法解背包問題；025 .量 量容的的品包物

7、背入入請請 請請 請請 請請請請 請請最皿IPP41 8I:皿 的的 品品 物物 入入 i:3:6 I:皿 的的 品品 物物 8 2 2 S 入入 i? 1 I:皿 的的 品品 物物 8 3 3 S 入入 i8 5 曰8: 的的 品品 物物 tM 4 4 入入 i9 曰8: 的的 品品 物物 85 入入 i75a t - n i 0 1 1 0 1 X 餐案昨5 要要要要要11 機品品品品品10 督物物物物： eeeessss 01234588四、實驗結(jié)果分析及總結(jié)（對實驗的結(jié)果是否達到預(yù)期進行分析，總結(jié)實驗 的收獲和存在的問題等）貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。 當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：不能保證求得的最后解是最佳的；不能用來求最大或最小解問題；只能求滿足某些約束條件的可行解的范圍。復(fù)雜性分析：對于該算法中，前兩個FOR循環(huán)的復(fù)雜度均為O（n），在WHILE循環(huán)中，求V中最大 值所對應(yīng)的下標采用建立最大堆的方式，其復(fù)雜度為O（logn），而且我們的V每一次循 環(huán)后在變小，所以上界是logn（即O（logn），WHILE循環(huán)中其他的操作都是常數(shù)級別的， 所以整個WHILE循環(huán)就是O（nlogn）。綜上，算法的時間復(fù)雜度為O（nlogn）。序列P1, P2,，Pn; W1,