貪心算法 實(shí)驗(yàn)報(bào)告

1、2009-2010 學(xué)年第一學(xué)期任課老師： 王璇實(shí)驗(yàn)題目設(shè)分治算法設(shè)計(jì)技術(shù)的 應(yīng)用實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)開始日期：2010/11/02報(bào)告提交日期：2010/11/10實(shí)驗(yàn)?zāi)康摹⒁髮?shí)驗(yàn)題目利用貪心策略解決背包問(wèn)題?，F(xiàn)有載重為M公斤的背包和n種貨物。第i種貨物的重量為 Wi,它的總價(jià)值為Pi,假定M、Wi、Pi均為整數(shù)。設(shè)計(jì)程序給出裝貨方法，使裝入背包的貨物總 價(jià)值達(dá)到最大。設(shè)計(jì)實(shí)現(xiàn)超市收銀程序，假設(shè)顧客在超市購(gòu)買各種商品，來(lái)到收銀臺(tái)結(jié)賬，收銀員具有面 值為100，20，10，5和1元的紙幣和各種面值為5角、2角、1角的硬幣。設(shè)計(jì)程序計(jì)算顧客各種 所買商品的錢數(shù)，并根據(jù)顧客所付的錢數(shù)輸出零錢的數(shù)目及要找

2、的各種貨幣的數(shù)目。實(shí)驗(yàn)設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)及說(shuō)明使用的是數(shù)組，分別定義商品的價(jià)格很商品的質(zhì)量。int p口 =25, 24, 15; /貨物的價(jià)值int w口 =18, 15, 10; /貨物的重量使用的是數(shù)組，存放各種面值錢幣int a9 = 1000,500,200,100,50,10,5,2,1;用層次圖描述程序結(jié)構(gòu)，并說(shuō)明程序各函數(shù)的名稱、功能， 圖示各函數(shù)之間相互的調(diào)用關(guān)系。第一題：int main(void)print(x, N)打印double型數(shù)組greedySolve(p, w, N, M) 調(diào)用print(x, N)打印double型數(shù)組貪心算法求比率調(diào)用findMax(r, n

3、)返回最大值的下標(biāo)第二題：略各個(gè)函數(shù)的設(shè)計(jì)及說(shuō)明第一題：/貪心算法求解，返回double數(shù)組，每一個(gè)位對(duì)應(yīng)著相應(yīng)的貨物要裝入的比率 double* greedySolve(int* p, int* w, int n, int m)double* r = (double*)malloc(sizeof(double)*n);/初 始化指針 double* s = (double*)malloc(sizeof(double)*n);int i;for(i=0; in; i+)ri = pi/(wi*1.0);/求單價(jià)通過(guò)這個(gè)函數(shù)求出每個(gè)商品的單價(jià)，并調(diào)用void print（double* arra

4、y, int size） 打印出單價(jià)的一維 double 數(shù)組。循環(huán)調(diào)用 int findMax（double* array, int size） 返回單價(jià)最大的商品的下標(biāo)（將前一個(gè)最大值賦值為-1），將商品根據(jù)單價(jià)由大到小 裝進(jìn)背包。最后計(jì)算背包中每種商品的比例，并返回值。（可通過(guò)更改數(shù)組跟宏定義 來(lái)改變數(shù)據(jù)）第二題：int a9 = 1000,500,200,100,50,10,5,2,1;/定義一個(gè)存放各種面值錢幣的數(shù)組 （單位為角）由用戶決定需要轉(zhuǎn)換的金錢的總額for（int i=0;i=ai）/當(dāng)錢額小于面值時(shí)退出循環(huán)money二money-ai;/當(dāng)前金額減去面值tmpMoney+

5、;/保存當(dāng)前面值的張數(shù)printf（%d 元的張數(shù)為：%dn，ai,tmpMoney）;tmpMoney=0;/把這下一次的數(shù)量清零（5）測(cè)試數(shù)據(jù)的設(shè)計(jì)及預(yù)期結(jié)果第一題：測(cè)試數(shù)據(jù)為：int p口 =25, 24, 15; /貨物的價(jià)值 int w口 =18, 15, 10; /貨物的重量 const int N = 3; /貨物種類的總數(shù) const int M = 20; /背包的大小 （可通過(guò)更改數(shù)組跟宏定義來(lái)改變數(shù)據(jù)）1 .39 1.60 1.50?k00 1.00 0.50Process retLLi-ned 0 execution time : 0-671Press any key to c q n t in Lie.第二題:1 rigs Arirnini stra tor戛面 頭碧四隋輸入商品總價(jià)能0 餡卷入顧錢數(shù)泓眼 抑如元的張翱為，冬 通元的成藪為M 1 /鼬元的明藪為M 2 壬雄元的登藪為f 飽元知張數(shù)為=1 拘元的盤數(shù)為=4 5元的張數(shù)為=輕 Z元的張數(shù)為=快 直元的成數(shù)為=快IPtocess ieturned 0 execution t ine - 11.828 s IPtess any key to continue .測(cè)試數(shù)據(jù)也預(yù)期結(jié)果相同。（6）總結(jié)及心得體會(huì)：此次實(shí)驗(yàn)讓我對(duì)貪心算法的思想有了初步的了解，并且學(xué)會(huì)了用貪心算法解決