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

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

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

2、所買商品的錢數(shù)，并根據(jù)顧客所付的錢數(shù)輸出零錢的數(shù)目及要找的各種貨幣的數(shù)目。二、實(shí)驗(yàn)要求1.該實(shí)驗(yàn)的課內(nèi)學(xué)時(shí)是4個(gè)課吋。2.題目1必須完成。3.題Fl1在完成上述基本功能的前提下，有能力的同學(xué)可以完成題目2。實(shí)驗(yàn)步驟與內(nèi)容(t)實(shí)驗(yàn)叔針的數(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請(qǐng)盛人貨物的數(shù)目n:rT);scanf("%d",&n);p

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

4、j+l];value[j+l]=t;〃按貨物的單位重量?jī)r(jià)值進(jìn)行排序q二W[j];W[j]岬[j+1];W[j+1]二q;//相應(yīng)的貨物重量進(jìn)行排序}}printfC單位價(jià)值量(從大到小)如下：");for(i=l;i〈=n;i++)printf(，z%5.2fvalueti]);printf("");printff所對(duì)應(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];//計(jì)算總價(jià)值x[i]二W[i];s二i;s++;if(M<=W[s]){values二values+M*value[s];//如果背包的負(fù)重小于貨物的重量時(shí),則裝貨量等于背包的剩奈載重xL++iJ=M;M=0;i++；printf(裝貨方式如下：);for(i=l;i〈=n;i++)printf(，z%5.2f"、x[i]);printf;printf("最大價(jià)值為: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請(qǐng)輸入商品的數(shù)目：〃);scanf&n);printf(/z輸入每彳牛商品的價(jià)格:〃)；for(i=l;i<=n;i++){printf(，z第％(1件："，i);seanf&price);total二total+price;}printfC"總的價(jià)格=%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張?，);