程序設(shè)計貪心算法

《程序設(shè)計貪心算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實驗報告2011?2012學(xué)年第_2_學(xué)期任課老師：課程名稱班級座號姓名實驗題目貪心算法設(shè)計技術(shù)的應(yīng)用實驗時間實驗開始日期：2012.4.20報告提交日期：2012.4.30實驗?zāi)康?、要求一、實驗題目1.利用貪心策略解決背包問題?，F(xiàn)有載重為M公斤的背包和n種貨物。第i種貨物的重量為Wi,它的總價值為Pi,假定M、W'i、Pi均為整數(shù)。設(shè)計程序給出裝貨方法，使裝入背包的貨物總價值達到最大。2.設(shè)計實現(xiàn)超市收銀程序，假設(shè)顧客在超市購買各種商品，來到收銀臺結(jié)賬，收銀員具有面值為100,20,10,5和1元的紙幣和各種面值為5角、2角、1角的硬幣。設(shè)計程序計算顧客各種

2、所買商品的錢數(shù)，并根據(jù)顧客所付的錢數(shù)輸出零錢的數(shù)目及要找的各種貨幣的數(shù)目。二、實驗要求1.該實驗的課內(nèi)學(xué)時是4個課吋。2.題目1必須完成。3.題Fl1在完成上述基本功能的前提下，有能力的同學(xué)可以完成題目2。實驗步驟與內(nèi)容(t)實驗叔針的數(shù)據(jù)無枸數(shù)組floatP[20],W[20],value[20],x[20];①背包voidpackbag()inti,j,n,s二0;floatP[20],W[20],value[20],x[20],values二0;floatq二0,t二0,M二0;printfC請盛人貨物的數(shù)目n:rT);scanf("%d",&n);p

3、rintfC請輸入背包的負(fù)重M:rT);scanf("%f",&M);printfC請輸入各種貨物的重量:〃)；for(i=l;i<=n;i++)scanf(%f〃,&W[i]);printff請輸入各種貨物的價值:〃)；for(i=l;i<=n;i++)scanf(飩f",&P[i]);for(i=l;i<=n;i++)value[i]=P[i]/W[i];//計算貨物的單位重量價值for(i=l;i<=n;i++){for(j=l;jE-i;j++)if(value[j]

4、j+l];value[j+l]=t;〃按貨物的單位重量價值進行排序q二W[j];W[j]岬[j+1];W[j+1]二q;//相應(yīng)的貨物重量進行排序}}printfC單位價值量(從大到小)如下：");for(i=l;i〈=n;i++)printf(，z%5.2fvalueti]);printf("");printff所對應(yīng)的貨物重量如下:『);for(i=l;i<=n;i++)printfC%5.2f",W[i]);printfU");i=l；while(M!=0){M-二W[i];//背包負(fù)重遞減values二values+w[i]*value[

5、i];//計算總價值x[i]二W[i];s二i;s++;if(M<=W[s]){values二values+M*value[s];//如果背包的負(fù)重小于貨物的重量時,則裝貨量等于背包的剩奈載重xL++iJ=M;M=0;i++；printf(裝貨方式如下：);for(i=l;i〈=n;i++)printf(，z%5.2f"、x[i]);printf;printf("最大價值為:values=%5.2f",values);}printf;②收銀系統(tǒng)voidmoneysys()doubleprice,total=0,givemoney,leamoney;in

6、tn,i,k=0,m=0,x=0,y=0;printfC請輸入商品的數(shù)目：〃);scanf&n);printf(/z輸入每彳牛商品的價格:〃)；for(i=l;i<=n;i++){printf(，z第％(1件："，i);seanf&price);total二total+price;}printfC"總的價格=%5.2frT,total);printfC'輸入頗孝所給的錢:〃)；seanf(〃％1產(chǎn),&givemoney);leamoney=givemoney-totai;printf余的錢為%5.2f，z,leamoney);printfC#

7、種貨幣藥藪自如卞:;whi1e(1eamoney>=100){1eamoney=learnoney-100;k++;if(1eamoney<100)}printf(，z100元二%d張",k);while(leamoney>=20)1eamoney=learnoney-20;x++;if(leamoney<20)printf(z，20元或d張x);while(1eamoney>=10){leamoney=leamoney-10;printf(〃1070=1張〃);}.while(1eamoney>=5){1eamoney=learnoney-5;}

8、printf("5元二1張?，);