北郵算法作業(yè)貪心算法實驗報告

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

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

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

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

4、0378233753599109421535695169120396982285454110242676546SampleOutput:Case1:134Case2:0Case3:109Case4:212Case5:312問題分析:本題是特殊的01背包問題，由于其價值和重量的反比規(guī)律易證明貪婪算法的有效性，故本題可以采用貪心算法求解，即每次優(yōu)選最輕物品也是最大價值物品。源代碼：（僅附文件輸入輸出版本，標準輸入輸出版本見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