數(shù)據(jù)結(jié)構(gòu)常見問題：12單元23 背包問題

《數(shù)據(jù)結(jié)構(gòu)》課程常見問題

一一單元23背包問題

i.背包問題如何用求解？

解析：

一、問題描述

0/1背包問題：

現(xiàn)有n種物品，對l〈=i<=n,已知第i種物品的重量為正整數(shù)Wi,價值為正整數(shù)Vi,背包能承受的最大

載重量為正整數(shù)肌現(xiàn)要求找出這n種物品的一個子集，使得子集中物品的總重量不超過W且總價值盡量

大。(注意：這里對每種物品或者全取或者一點都不取，不允許只取一部分)

二、算法分析

根據(jù)問題描述，可以將其轉(zhuǎn)化為如下的約束條件和目標函數(shù):

于是，問題就歸結(jié)為尋找一個滿足約束條件(1),并使目標函數(shù)式(2)達到最大的解向量。

首先說明一下0-1背包問題擁有最優(yōu)解。

假設(shè)是所給的問題的一個最優(yōu)解，則是下面問題的一個最優(yōu)解：。如果不是的話，設(shè)是這個問題的

一個最優(yōu)解，則，且。因此，，這說明是所給的0T背包問題比更優(yōu)的解，從而與假設(shè)矛盾。

窮舉法：

用窮舉法解決0-1背包問題，需要考慮給定n個物品集合的所有子集，找出所有可能的子集(總重量不

超過背包重量的子集)，計算每個子集的總重量，然后在他們中找到價值最大的子集。由于程序過于簡單,

在這里就不再給出，用實例說明求解過程。下面給出了4個物品和一個容量為10的背包，下圖就是用窮

舉法求解0T背包問題的過程。

(a)四個物品和一個容量為10的背包

序號子集總重量總價值序號子集總重量總價值

1空集009{2,3}752

2{1}74210{2,4}837

3{2}31211{3,4}965

4{3}44012(1,2,3}14不可行

5{4}52513(1,2,4}15不可行

6{1,2}105414{1,3,4)16不可行

7{1,3}11不可行15{2,3,4}12不可行

8{1,4}12不可行16{1,2,3,4}19不可行

(b)用回溯法求解0T背包問題的過程

遞歸法：

在利用遞歸法解決0-1背包問題時，我們可以先從第n個物品看起。每次的遞歸調(diào)用都會判斷兩種情況:

(1)背包可以放下第n個物品，則x[n]=l,并繼續(xù)遞歸調(diào)用物品重量為W-w[n],物品數(shù)目為n-1的遞

歸函數(shù)，并返回此遞歸函數(shù)值與v[n]的和作為背包問題的最優(yōu)解；

(2)背包放不下第n個物品，則x[n]=0,并繼續(xù)遞歸調(diào)用背包容量為肌物品數(shù)目為nT的遞歸函數(shù),

并返回此遞歸函數(shù)值最為背包問題的最優(yōu)解。

遞歸調(diào)用的終結(jié)條件是背包的容量為0或物品的數(shù)量為0.此時就得到了0T背包問題的最優(yōu)解。

用遞歸法解0-1背包問題可以歸結(jié)為下函數(shù)：

第一個式子表示選擇物品n后得到價值比不選擇物品n情況下得到的價值小，所以最終還是不選擇

物品n;第二個式子剛好相反，選擇物品n后的價值不小于不選擇物品n情況下得到了價值，所以最終選

擇物品no

在遞歸調(diào)用的過程中可以順便求出所選擇的物品。下面是標記物品被選情況的數(shù)組x[n]求解的具體函

數(shù)表示：

在函數(shù)中，遞歸調(diào)用的主體函數(shù)為KnapSack,m表示背包的容量，n表示物品的數(shù)量，x[n]表示是

否選擇了第n個物品（1一選，0一不選）。每個物品的重量和價值信息分別存放在數(shù)組w[n]和v[n]中。具

體的代碼見《遞歸法》文件夾。

貪心法：

0-1背包問題與背包問題類似，所不同的是在選擇物品裝入背包時，可以選擇一部分，而不一定要全部

裝入背包.這兩類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，相當相似。但是背包問題可以用貪心法求解，而0-1背包

問題卻不能用貪心法求解。貪心法之所以得不到最優(yōu)解，是由于物品不允許分割，因此，無法保證最終能

將背包裝滿，部分閑置的背包容量使背包單位重量的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比

較選擇物品和不選擇物品所導(dǎo)致的方案，然后做出最優(yōu)解。由此導(dǎo)出了許多相互重疊的子問題，所以，0-1

背包問題可以用動態(tài)規(guī)劃法得到最優(yōu)解。在這里就不再用貪心法解0-1背包問題了。

動態(tài)規(guī)劃法分析：

0-1背包問題可以看作是尋找一個序列，對任一個變量的判斷是決定=1還是=0.在判斷完之后，

已經(jīng)確定了，在判斷時，會有兩種情況：

（I）背包容量不足以裝入物品i,則=0,背包的價值不增加；

（2）背包的容量可以裝下物品i,則=1,背包的價值增加。

這兩種情況下背包的總價值的最大者應(yīng)該是對判斷后的價值。令表示在前i個物品中能夠裝入容量為

j的背包的物品的總價值，則可以得到如下的動態(tài)規(guī)劃函數(shù)：

式（1）說明：把前面i個物品裝入容量為。的背包和把0個物品裝入容量為j的背包，得到的價

值均為0.式（2）第一個式子說明：如果第i個物品的重量大于背包的容量，則裝入第i個物品得到的最

大價值和裝入第i-1個物品得到的最大價值是相同的，即物品i不能裝入背包中；第二個式子說明：如果

第i個物品的重量小于背包的容量，則會有兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的

價值就等于把前i-1個物品裝入容量為的背包中的價值加上第i個物品的價值：（2）如果第i個物品沒

有裝入背包，則背包中物品的價值就是等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，

取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。

我們可以一步一步的解出我們所需要的解。第一步，只裝入第一個物品，確定在各種情況下背包

能得到的最大價值；第二步，只裝入前兩個物品，確定在各種情況下的背包能夠得到的最大價值；一次類

推，到了第n步就得到我們所需要的最優(yōu)解了。最后，便是在容量為W的背包中裝入n個物品時取得的

最大價值。為了確定裝入背包的具體物品，從的值向前尋找，如果＞，說明第n個物品被裝入了背包中，

前n-1個物品被裝入容量為的背包中；否則，第n個物品沒有裝入背包中，前n-1個物品被裝入容量為W

的背包中。依此類推，直到確定第一個物品是否被裝入背包為止。由此，我們可以得到如下的函數(shù)：.

根據(jù)動態(tài)規(guī)劃函數(shù)，用一個的二維數(shù)組C存放中間變量，表示把前i個物品裝入容量為j的背

包中獲得的最大價值。

設(shè)物品的重量存放在數(shù)組w[n]中，價值存放在數(shù)組v[n]中，背包的容量為W,數(shù)組存放迭代的結(jié)

果，數(shù)組x[n]存放裝入背包的物品，動態(tài)規(guī)劃解0T背包問題的源代碼在文件夾《動態(tài)規(guī)劃法》中。

回溯法分析：

用回溯法解0」背包問題時，會用到狀態(tài)空間樹。在搜索狀態(tài)空間樹時，只要其左兒子結(jié)點是一個可行

結(jié)點，搜索就進入其左子樹。當右子樹有可能包含最優(yōu)解時才進入右子樹搜索，否則將右子樹剪去。設(shè)r

是當前剩余物品價值總和；cp是當前價值；bestp是當前最優(yōu)價值。當cp+rWbestp時，可剪去右子樹。

計算右子樹中解的上界可以用的方法是將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不

下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是右子樹中解的上界，用此值來剪枝。

為了便于計算上界，可先將物品依其單位重量價值從大到小排序，此后只要順序考察各物品即可。在實

現(xiàn)時，由MaxBoundary函數(shù)計算當前結(jié)點處的上界。它是類Knap的私有成員。Knap的其他成員記錄了解

空間樹種的節(jié)點信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時所需要的?？臻g。在解空間樹的當前擴展結(jié)

點處，僅當要進入右子樹時才計算上界函數(shù)MaxBoundary,以判斷是否可以將右子樹減去。進入左子樹時

不需要計算上界，因為其上界與父結(jié)點的上界相同。

在調(diào)用函數(shù)Knapsack之前，需要先將各物品依其單位重量價值從達到小排序。為此目的，我們定義了

類Objiect。其中，運算符與通常的定義相反，其目的是為了方便調(diào)用已有的排序算法。在通常情況下，

排序算法將待排序元素從小到大排序。

在搜索狀態(tài)空間樹時，由函數(shù)Backtrack控制。在函數(shù)中是利用遞歸調(diào)用的方法實現(xiàn)了空間樹的搜索。

具體的代碼見《回溯法》文件夾。

限界分支法：

在解0-1背包問題的優(yōu)先隊列式界限分支法中，活結(jié)點優(yōu)先隊列中結(jié)點元素N的優(yōu)先級由該結(jié)點的上界

函數(shù)MaxBoundary計算出的值uprofit給出。該上界函數(shù)在07背包問題的回溯法總已經(jīng)說明過了。子集

樹中以結(jié)點N為根的子樹中任一個結(jié)點的價值不超過N.profit,因此我們用一個最大堆來實現(xiàn)活結(jié)點優(yōu)先

隊列。堆中元素類型為HeapNode,其私有成員有uprofit,profit,weight,level,和ptr。對于任意一個活

結(jié)點N,N.weight是活結(jié)點N所相應(yīng)的重量；1profit是N所相應(yīng)的價值；N.uprofit是結(jié)點N的價值上

界，最大堆以這個值作為優(yōu)先級。子集空間樹中結(jié)點類型為bbnode。

在分支限界法中用到的類Knap與0T背包問題的回溯法中用到的類Knap很相似。他們的區(qū)別是新的類

中沒有了成員變量bestp,而增加了新的成員bestx。Bestx[i]=l,當且僅當最優(yōu)解含有物品i。

在類Knap中有四個函數(shù)：

(1)上界函數(shù)MaxBoundary(),計算節(jié)點所對應(yīng)價值的上界：

(2)函數(shù)AddLiveNodeO是將一個新的活結(jié)點插入到子集樹和優(yōu)先隊列中；

(3)函數(shù)MaxKnapsackO實施對子集樹的優(yōu)先隊列式分支界限搜索。其中假定物品依其單位價值從大

到小已經(jīng)排好序。相應(yīng)的排序過程會在算法的預(yù)處理部分完成。算法中E是當前擴展結(jié)點；cw是該結(jié)點的

重量；cp是該結(jié)點的價值；up是價值上界。算法的while循環(huán)不斷擴展結(jié)點，直到子集樹的一個葉結(jié)點

成為擴展結(jié)點為止。此時優(yōu)先隊列中所有活結(jié)點的價值上界均不超過該葉結(jié)點的價值。因此該葉結(jié)點相應(yīng)

的解為問題的最優(yōu)解。

在while循環(huán)內(nèi)部，算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點,

則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點

滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。

(4)函數(shù)Knapsack()完成對輸入數(shù)據(jù)的處理。其主要任務(wù)是將各物品依其單位重量價值從達到小排好

序。然后調(diào)用函數(shù)MaxKnapsackO完成對子集樹的優(yōu)先隊列式分支限界搜索。

具體的實現(xiàn)代碼在文件夾《分支限界法》中。

三、時空效率分析

窮舉法：

對于一個有n個元素的集合，其子集數(shù)量為，所以，不論生成子集的算法效率有多高，窮舉法都會

導(dǎo)致一個的算法。

遞歸法：

在遞歸法的算法體中有一個if判斷中出現(xiàn)了兩次遞歸調(diào)用比較大小所以它們之間的遞歸關(guān)系式可

以大體表示為：，其中表示遞歸法的時間復(fù)雜度，C是常數(shù)。求解遞歸方程可以知道的量級為。所以

遞歸法解0T背包問題的時間復(fù)雜度為。遞歸法是耗費空間最多的算法，每次遞歸調(diào)用都需要壓棧，導(dǎo)

致棧的使用很頻繁。

動態(tài)規(guī)劃法：

由于函數(shù)Knapsack中有一個兩重for循環(huán)，所以時間復(fù)雜度為0[(n+1)x(m+l)].空間復(fù)復(fù)雜度也

是0[(n+1)x(m+1)],即0(nm).

回溯法：

由于計算上界的函數(shù)MaxBoundary需要0(n)時間，在最壞情況下有個右兒子結(jié)點需要計算上界，所以

解0T背包問題的回溯法算法BackTrack所需要的計算時間為.

限界分支法：

在使用限界分治法時，就是使用更好的限界剪枝函數(shù)使得不必要的解被剔除，但是在最壞情況下

的解仍然是和回溯法是相同的。本算法中也是用到了計算上界的函數(shù)MaxBoundary需要0(n)的時間，而且

在最壞情況下有個結(jié)點需要計算上界，所以在最壞情況下的時間復(fù)雜度仍然為。

四、運行結(jié)果

遞歸法輸出結(jié)果：

動態(tài)規(guī)劃法輸出結(jié)果:

回溯法輸出結(jié)果:

分枝限界法輸出結(jié)果:

五、分析輸出結(jié)果

上面測試的是每種算法在兩種輸入情況下得到的0T背包問題的解。兩種測試數(shù)據(jù)為:

第一組：背包容量：18；物品數(shù)目：7；

每個物品重量為：112489610；

每個物品價值為：7881213414。

第二組：背包容量：50；物品數(shù)目：10；

每個物品重量為：81224166935211819；

每個物品價值為：34325667543245564670。

四種實現(xiàn)的算法中，只有回溯法沒能夠得到預(yù)期的最優(yōu)解。(