背包問(wèn)題系列算法詳解

1、背包問(wèn)題系列算法詳解背包問(wèn)題是一個(gè)關(guān)于最優(yōu)解的經(jīng)典問(wèn)題。通常被討論的最多的，最經(jīng)典的背包問(wèn)題是0-1背包問(wèn)題(0-1 Knapsack Problem)o它是一切背包問(wèn)題及相關(guān)背包問(wèn)題的基礎(chǔ)。本篇博文將詳 細(xì)分析0-1背包問(wèn)題，并給出 0-1背包問(wèn)題的幾種解法，同時(shí)也對(duì)0-1背包問(wèn)題的內(nèi)涵進(jìn)行延伸，豐富其外延至完全背包問(wèn)題和多重背包問(wèn)題，并給出背包問(wèn)題的算法實(shí)現(xiàn)過(guò)程，希望對(duì)大家有幫助。一、0-1背包問(wèn)題有N件物品和一個(gè)容量為V的背包。第i件物品(每個(gè)物品只有一件)的費(fèi)用是ci,價(jià)值是wi。求解將哪些物品裝入背包可使價(jià)值總和最大。(1)遞歸求解算法如下：#include iostream#def

2、ine CAPACITY 10#define GOODSNUM 6using namespace std;int nVolGOODSNUM;int nValueGOODSNUM;int knapsack(int itemIndex,int vol);void main() int i=0,j=0; while(iGOODSNUM) coutinput the i+1nVolinValuei;i+;coutThe max value is: knapsack(GOODSNUM,CAPACITY)=nVolitemIndex&knapsack(itemIndex-1,vol)knapsack(it

3、emIndex-1,vol-nVolitemIndex)+nValueitemIndex)return knapsack(itemIndex-1,vol-nVolitemIndex)+nValueitemIndex; elsereturn knapsack(itemIndex-1,vol);)分析：遞歸求解，求解過(guò)程中的絕大部分變量存在重復(fù)求解的過(guò)程，算法的效率較低，有待改進(jìn)；那怎么改進(jìn)呢？最有效的是用數(shù)組保存每次計(jì)算的結(jié)果，不用重復(fù)計(jì)算，于是有二維數(shù)組求解。(2)二維數(shù)組求解 算法如下：#include iostream#define CAPACITY 10#define GOODSNUM

4、6 using namespace std; void main() int i=1,j;int vGOODSNUM = 10,12,40,40,40,15;int cGOODSNUM = 1,2,3,5,2,1;int funGOODSNUM+1CAPACITY+1;for (i=1;i=GOODSNUM;i+) funi0 = 0;for (i=1;i=CAPACITY;i+) fun0i = 0;for (i=1;i=GOODSNUM;i+)for (j=1;j=CAPACITY;j+)if (jci-1)funij = funi-1j;else if (funi-1jfuni-1j-c

5、i-1 + vi-1) funij = funi-1j-ci-1 + vi-1;elsefunij = funi-1j;coutThe max value is: funGOODSNUMCAPACITYendl;分析：二維數(shù)組求解方法相比遞歸求解要優(yōu)越很多，但是其空間復(fù)雜度依然較高，還有 繼續(xù)改進(jìn)的余地嗎？ 一維數(shù)組是否可行呢？答案是肯定的(3) 一維數(shù)組求解 算法分析：#include iostream#define CAPACITY 10#define GOODSNUM 6 using namespace std; void main()int nVolumeGOODSNUM = 1,2,

6、3,5,2,1;int nValueGOODSNUM = 10,12,40,40,40,15;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;most important for the first compution below int itemIndex,capIndex;for (itemIndex=0;itemIndex=nVolumeitemIndex;capIndex-)noticethatcapIndex=nVolumeitemIndex,not capIndex=0注意此處與二維數(shù)組求解的區(qū)別i

7、f (nKnapsackcapIndexnKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex)nKnapsackcapIndex = nKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex; selectTableitemIndexcapIndex = 1;elsenKnapsackcapIndex = nKnapsackcapIndex;coutThe max value is: nKnapsackCAPACITYendl;cout=0;itemIndex-)if (selectTableitemI

8、ndexcapIndex)coutitemIndex+1;capIndex = capIndex - nVolumeitemIndex; coutendl;分析：在一維數(shù)組實(shí)現(xiàn)中將空間復(fù)雜度由O(GOODSNUM*CAPACITYf低至iJ O(CAPACITY同時(shí)進(jìn)行了代碼優(yōu)化，同時(shí)也給出了選擇物品的編號(hào)。二、完全背包問(wèn)題若你能給深入理解 0-1背包問(wèn)題和其深刻內(nèi)涵，并真正明白一維數(shù)組求解背包問(wèn)題后， 下面的問(wèn)題對(duì)你來(lái)說(shuō)就相當(dāng)容易了。完全背包問(wèn)題：有 N種物品和一個(gè)容量為 V的背包，每種物品都有無(wú)限件可用。第 i種 物品的費(fèi)用是 ci,價(jià)值是wio求解將哪些物品裝入背包可使這些物品的費(fèi)用總和

9、不超過(guò) 背包容量，且價(jià)值總和最大。求解分析：目標(biāo)是轉(zhuǎn)化為 0-1背包問(wèn)題。如將費(fèi)用/容量為nVolumeitemIndex的物品轉(zhuǎn) 化為CAPACITY /nVolumeitemIndex相同費(fèi)用和價(jià)值的物品，直接用前面的三種 0-1背包問(wèn)題求解。除此之外還有其它可行的求解方法嗎？可以對(duì)0-1背包問(wèn)題的狀態(tài)方程 fiv=maxfi-1v,fi-1v-ci+wi 稍加分析可得完全背包問(wèn) 題的狀態(tài)方程fi v=maxfi-1v-k*ci+k*wi0=k*ci=v,因而有以下算法實(shí)現(xiàn)過(guò)程，并最終給出了所選 擇的物品和選擇該物品的數(shù)目。實(shí)現(xiàn)算法：#include iostream#define CAP

10、ACITY 10#define GOODSNUM 6using namespace std;void main() int num,k,max;int nVolumeGOODSNUM = 1,4,3,5,5,3;int nValueGOODSNUM = 2,8,40,60,10,3;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;/most important for the first compution belowint itemIndex,capIndex;for (itemIndex=0;itemInd

11、ex=nVolumeitemIndex;capIndex-)/notice that capIndex=nVolumeitemIndex,not capIndex=0num = 0;max = nKnapsackcapIndex;for (k=1;k=k*nVolumeitemIndex&maxnKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex)max = nKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex;num = k;nKnapsackcapIndex = max;sele

12、ctTableitemIndexcapIndex = num; coutThe max value is: nKnapsackCAPACITYendl;coutThe selected items are: =0;itemIndex-)(if (selectTableitemIndexcapIndex)(coutitemIndex+1:selectTableitemIndexcapIndex;capIndex = capIndex - selectTableitemIndexcapIndex*nVolumeitemIndex;)coutendl;)三、多重背包問(wèn)題多重背包問(wèn)題：有N種物品和一個(gè)容量為V的背包。第i