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

1、實(shí)驗(yàn)四“01”背包問題一、一、實(shí)驗(yàn)?zāi)康呐c要求實(shí)驗(yàn)?zāi)康呐c要求熟悉CC語言的集成開發(fā)環(huán)境；通過本實(shí)驗(yàn)加深對(duì)貪心算法、動(dòng)態(tài)規(guī)劃算法的理解。二、二、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容:掌握貪心算法、動(dòng)態(tài)規(guī)劃算法的概念和基本思想，分析并掌握“01”背包問題的求解方法，并分析其優(yōu)缺點(diǎn)。三、三、實(shí)驗(yàn)題實(shí)驗(yàn)題1.“01”背包問題的貪心算法2.“01”背包問題的動(dòng)態(tài)規(guī)劃算法說明：背包實(shí)例采用教材P132習(xí)題六的61中的描述。要求每種的算法都給出最大收益和最優(yōu)解。設(shè)有背包問

2、題實(shí)例n=7，M=15，(w0w1。。。w6)=（2357141），物品裝入背包的收益為：（p0，p1，。。。，p6）=（1051576183）。求這一實(shí)例的最優(yōu)解和最大收益。四、四、實(shí)驗(yàn)步驟實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。五、五、實(shí)驗(yàn)程序?qū)嶒?yàn)程序bound=exchangeexchange=0f(inti=0i0)arry_x[i]=arry_w[i]把