資源描述:
《北郵算法作業(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