0-1背包問題-貪心法和動態(tài)規(guī)劃法求解1

1、實(shí)驗(yàn)四“0-1”背包問題實(shí)驗(yàn)?zāi)康呐c要求熟悉C/C+語言的集成開發(fā)環(huán)境；通過本實(shí)驗(yàn)加深對貪心算法、動態(tài)規(guī)劃算法的理解。實(shí)驗(yàn)內(nèi)容：掌握貪心算法、動態(tài)規(guī)劃算法的概念和基本思想，分析并掌握“0-1”背包問題的求解方法，并分析其優(yōu)缺點(diǎn)。實(shí)驗(yàn)題“0-1”背包問題的貪心算法“0-1”背包問題的動態(tài)規(guī)劃算法說明：背包實(shí)例采用教材P132習(xí)題六的6-1中的描述。要求每種的算法都給出最大收益和最優(yōu)解。設(shè)有背包問題實(shí)例,。（），物品裝入背包的收益為：（，。，6（7求這一實(shí)例的最優(yōu)解和最大收益。實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報告。實(shí)驗(yàn)程序貪

2、心法求解按照單位物品收益排序，傳入?yún)?shù)單位物品收益，物品收益和物品重量的數(shù)組，運(yùn)用冒泡排序獲取最優(yōu)解方法，傳入?yún)?shù)為物品收益數(shù)組，物品重量數(shù)組，最后裝載物品最優(yōu)解的數(shù)組和還可以裝載物品的重量物品重量數(shù)組物品收益數(shù)組單位毒品的收益數(shù)組最后裝載物品的最優(yōu)解數(shù)組背包所能的載重最后的收益輸出最后的收益按照單位物品收益排序，傳入?yún)?shù)單位物品收益，物品收益和物品重量的數(shù)組，運(yùn)用冒泡排序求出物品的單位收益把求出的單位收益排序，冒泡排序法交換單位收益數(shù)組交換收益數(shù)組交換重量數(shù)組獲取最優(yōu)解方法，傳入?yún)?shù)為物品收益數(shù)組，物品重量數(shù)組，最后裝載物品最優(yōu)解的數(shù)組和還可以裝載物品的重量循環(huán)變量最后收益把當(dāng)前物品重量繳入

3、最優(yōu)解數(shù)組收益增加當(dāng)前物品收益背包還能載重量減去當(dāng)前物品重量輸出最優(yōu)解返回最后收益while(k=h&w2kww)(p2next=p2k;w2next=w2k;next+;k+;)if(k=h&w2k=ww)(if(ppp2next-1)(p2next=pp;w2next=ww;next+;)while(k=h&p2k=p2next-1)k+;)while(k=h)(p2next=p2k;w2next=w2k;next=next+1;k+;)l=h+1;h=next-1;Fi+1=next;)for(i=1;i0;i-)(next=Fi;next-;pp=pk=p2next;ww=w2next;while(ww+wiM&nextFi-1)(next=next-1;pp=p2next;實(shí)驗(yàn)結(jié)果1、貪心法截圖：-aAzr-X&lq&JLtF:耨叁嘗情匚+5tudyC-n-ProgramAlgorithmDe