-背包問(wèn)題求解方法綜述

《-背包問(wèn)題求解方法綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、算法分析與設(shè)計(jì)大作業(yè)實(shí)驗(yàn)題目：0-1背包問(wèn)題求解方法綜述組員：班　　級(jí)：指導(dǎo)老師：0-1背包問(wèn)題求解方法綜述【摘要】：0-1背包問(wèn)題是一個(gè)經(jīng)典的NP-hard組合優(yōu)化問(wèn)題，現(xiàn)實(shí)生活中的很多問(wèn)題都可以以它為模型。本文首先對(duì)背包問(wèn)題做了闡述，然后用蠻力解法、動(dòng)態(tài)規(guī)劃算法、貪心算法和回溯解法對(duì)背包問(wèn)題進(jìn)行求解，分析了0-1背包問(wèn)題的數(shù)學(xué)模型,刻劃了最優(yōu)解的結(jié)構(gòu)特征,建立了求最優(yōu)值的遞歸關(guān)系式。最后對(duì)四種算法從不同角度進(jìn)行了對(duì)比和總結(jié)。【關(guān)鍵詞】：0-1背包問(wèn)題；蠻力解法；動(dòng)態(tài)規(guī)劃算法；貪心算法；回溯解法。0.引言0-1背包問(wèn)題是指給定n個(gè)物品,每個(gè)物品均有自己的價(jià)值vi和重量wi(i=1

2、,2,…,n),再給定一個(gè)背包,其容量為W。要求從n個(gè)物品中選出一部分物品裝入背包,這部分物品的重量之和不超過(guò)背包的容量,且價(jià)值之和最大。單個(gè)物品要么裝入,要么不裝入。很多問(wèn)題都可以抽象成該問(wèn)題模型,如配載問(wèn)題、物資調(diào)運(yùn)[1]問(wèn)題等,因此研究該問(wèn)題具有較高的實(shí)際應(yīng)用價(jià)值。目前,解決0-1背包問(wèn)題的方法有很多,主要有動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法、遺傳算法、粒子群算法、人工魚(yú)群算法、蟻群算法、模擬退火算法、蜂群算法、禁忌搜索算法等。其中動(dòng)態(tài)規(guī)劃、回溯法、分支限界法時(shí)間復(fù)雜性比較高,計(jì)算智能算法可能出現(xiàn)局部收斂,不一定能找出問(wèn)題的最優(yōu)解。文中在動(dòng)態(tài)規(guī)劃法的基礎(chǔ)上進(jìn)行了改進(jìn),提出一種求解

3、0-1背包問(wèn)題的算法,該算法每一次執(zhí)行總能得到問(wèn)題的最優(yōu)解,是確定性算法,算法的時(shí)間復(fù)雜性最壞可能為O(2n)。1.0-1背包問(wèn)題描述0-1背包問(wèn)題(KP01)是一個(gè)著名的組合優(yōu)化問(wèn)題。它應(yīng)用在許多實(shí)際領(lǐng)域,如項(xiàng)目選擇、資源分布、投資決策等。背包問(wèn)題得名于如何選擇最合適的物品放置于給定背包中。本文主要研究背包問(wèn)題中最基礎(chǔ)的0/1背包問(wèn)題的一些解決方法。為解決背包問(wèn)題，大量學(xué)者在過(guò)去的幾十年中提出了很多解決方法。解決背包問(wèn)題的算法有最優(yōu)算法和啟發(fā)式算法[2]，最優(yōu)算法包括窮舉法、動(dòng)態(tài)規(guī)劃法、分支定界法、圖論法等，啟發(fā)式算法包括貪心算法、遺傳算法、蟻群算法、粒子算法等一些智能算法。0-

4、1背包問(wèn)題一般描述為：給定n種物品和一個(gè)背包。物品i的重量是w(i)，其價(jià)值為v(i)，背包的容量為c。問(wèn)應(yīng)該如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問(wèn)題稱為0-1背包問(wèn)題。此問(wèn)題的形式化描述是，給定，要求找出一個(gè)n元0-1向量，使得，而且達(dá)到最大。數(shù)學(xué)模型：約束條件：，2.0-1背包問(wèn)題的求解算法2.1蠻力算法（bruteforcemethod）2.1.1基本思想：對(duì)于有n種可選物品的0/1背包問(wèn)題，其解空間由長(zhǎng)度為n的0-1向量

5、組成,可用子集數(shù)表示。在搜索解空間樹(shù)時(shí)，深度優(yōu)先遍歷，搜索每一個(gè)結(jié)點(diǎn)，無(wú)論是否可能產(chǎn)生最優(yōu)解，都遍歷至葉子結(jié)點(diǎn)，記錄每次得到的裝入總價(jià)值，然后記錄遍歷過(guò)的最大價(jià)值。2.1.2代碼實(shí)現(xiàn):#include#includeusingnamespacestd;#defineN100//最多可能物體數(shù)structgoods//物品結(jié)構(gòu)體{intsign;//物品序號(hào)intw;//物品重量intp;//物品價(jià)值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb){

6、returnan-1){if(bestP

7、stP;}intKnapSack1(intn,goodsa[],intC,intx[]){Force(0);returnbestP;}intmain(){goodsb[N];printf("物品種數(shù)n:");scanf("%d",&n);//輸入物品種數(shù)printf("背包容量C:");scanf("%d",&C);//輸入背包容量for(inti=0;i