北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告

ID:38330662

大?。?96.00 KB

頁數(shù):26頁

時(shí)間:2019-06-10

北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告_第1頁
北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告_第2頁
北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告_第3頁
北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告_第4頁
北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告_第5頁
資源描述:

《北郵算法作業(yè)貪心算法實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三次算法作業(yè)(貪心算法)姓名:吳迪班級(jí):08211312學(xué)號(hào):08211488班內(nèi)序號(hào)15摘要:本文為完成作業(yè)problem1,problem3,problem4,problem5的四道貪心算法題。備注:所有后綴為_ex的可執(zhí)行文件為文件輸入輸出模式的程序,比如problem1_ex.exe(所有算法實(shí)現(xiàn)代碼承諾為本人自己編寫并且截圖為實(shí)際有效截圖,所有程序均通過Dev-C++編譯器實(shí)際測(cè)試可以運(yùn)行)problem1特殊的01背包(原算法分析題4-3)問題描述:01背包是在N件物品取出若干件放在空間為C的背包里,每件物品的體積為W1,W2……Wn,與之相對(duì)應(yīng)的價(jià)值為P

2、1,P2……Pn,并取得最大價(jià)值。普通的01背包中物品的重量和價(jià)值沒有明確的關(guān)系,這里定義一種特殊的01背包:向背包中放入的物品的價(jià)值和體積成反比,也就是價(jià)值越高,體積越小,注意這里物品價(jià)值和體積的乘積并不是固定值。例如:如下的物品滿足這個(gè)“特殊的01背包”,5件物品:物品1,價(jià)值v=6,體積w=20物品2,價(jià)值v=1,體積w=60物品3,價(jià)值v=20,體積w=3物品4,價(jià)值v=15,體積w=15物品5,價(jià)值v=99,體積w=1假如我有一個(gè)容量為c的背包,c=20,那么選擇物品3、4、5可以獲得最大價(jià)值134。輸入:首先是一個(gè)整數(shù)t,代表測(cè)試數(shù)據(jù)的組數(shù)。每組測(cè)試數(shù)據(jù)首先

3、是兩個(gè)正整數(shù)n和c,n代表物品的個(gè)數(shù),c代表背包的最大容積。然后有n行整數(shù),每行有兩個(gè)整數(shù),分別代表物品的價(jià)值v和體積w。t的范圍是(1-100),n的范圍是(1-100000),c、v、w的范圍不超過四字節(jié)的int型。輸出:首先輸出測(cè)試數(shù)據(jù)的組號(hào),例如第一組的組號(hào)為“Case1:”,占一行。然后是一個(gè)整數(shù),代表可以取得的最大價(jià)值,占一行。SampleInput:552062016020315159911110010051092171011093181093872610229613961889171061714086278331783110676846151954551

4、0378233753599109421535695169120396982285454110242676546SampleOutput:Case1:134Case2:0Case3:109Case4:212Case5:312問題分析:本題是特殊的01背包問題,由于其價(jià)值和重量的反比規(guī)律易證明貪婪算法的有效性,故本題可以采用貪心算法求解,即每次優(yōu)選最輕物品也是最大價(jià)值物品。源代碼:(僅附文件輸入輸出版本,標(biāo)準(zhǔn)輸入輸出版本見cpp代碼文件)#include#includeusingnamespacestd;intgreedy_calcul

5、ate(int*v,int*w,constintn,constintc);intmain(){//inputintt;//testgroupnum1-100intn;//objectnum1-100000intc;//capacityint*v;int*w;fstreamin;fstreamout;in.open("problem1_input.txt",ios::in);out.open("problem1_output.txt",ios::out);in>>t;if(t>100

6、

7、t<1)out<<"errorinputoft!"<

8、i>n;if(n>100000

9、

10、n<1)out<<"errorinputofn!"<>c;if(c<=0)out<<"errorinputofc!"<>v[j];in>>w[j];}//outputout<<"Case"<

11、em("pause");return0;}intgreedy_calculate(int*v,int*w,constintn,constintc){unsignedintleast_weight=-1;intlw_num=0;intcount=0;inttotal_value=0;inttotal_weight=0;bool*x;x=newbool[n];for(inti=0;i

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭