1.背包問題介紹

背包問題不單單是一個簡單的算法問題，它本質(zhì)上代表了一大類問題，這類問題實(shí)際上是01線性規(guī)劃問題，其約束條件和目標(biāo)函數(shù)如下：

自從dd_engi在2007年推出《背包問題九講》之后，背包問題的主要精髓基本已道盡。本文沒有嘗試對背包問題的本質(zhì)進(jìn)行擴(kuò)展或深入挖掘，而只是從有限的理解（這里指對《背包問題九講》的理解）出發(fā)，幫助讀者更快地學(xué)習(xí)《背包問題九講》中的提到的各種背包問題的主要算法思想，并通過實(shí)例解釋了相應(yīng)的算法，同時給出了幾個背包問題的經(jīng)典應(yīng)用。

2.背包問題及應(yīng)用

dd_engi在《背包問題九講》中主要提到四種背包問題，分別為：01背包問題，完全背包問題，多重背包問題，二維費(fèi)用背包問題。本節(jié)總結(jié)了這幾種背包問題，并給出了其典型的應(yīng)用以幫助讀者理解這幾種問題的本質(zhì)。

2.101背包問題

（1）問題描述

有N件物品和一個容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

（2）狀態(tài)轉(zhuǎn)移方程

其中，f(i,v) 表示從前i件物品選擇若干物品裝到容量為v的背包中產(chǎn)生的最大價(jià)值。當(dāng)v=0時，f(i,v)初始化為0，表示題目不要求背包一定剛好裝滿，而f(i,v)=inf/-inf（正無窮或負(fù)無窮）表示題目要求背包一定要剛好裝滿。下面幾種背包類似，以后不再贅述。

（3） 偽代碼

從轉(zhuǎn)移方程上可以看出，前i個物品的最優(yōu)解只依賴于前i-1個物品最優(yōu)解，而與前i-2，i-3,…各物品最優(yōu)無直接關(guān)系，可以利用這個特點(diǎn)優(yōu)化存儲空間，即只申請一個一維數(shù)組即可，算法時間復(fù)雜度（O(VN)）為:

for i=1..N
 
  for v=V..0
 
    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍歷順序?。?！

下面幾種背包用到類似優(yōu)化，以后不再贅述。

（4） 舉例

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

計(jì)算順序是：從右往左，自上而下：

（2）背包剛好裝滿

計(jì)算順序是：從右往左，自上而下。注意初始值，其中-inf表示負(fù)無窮

（5） 經(jīng)典題型

[1] 你有一堆石頭質(zhì)量分別為W1,W2,W3…WN.(W＜＝100000,N <30)現(xiàn)在需要你將石頭合并為兩堆，使兩堆質(zhì)量的差為最小。

[2] 給一個整數(shù)的集合，要把它分成兩個集合，要兩個集合的數(shù)的和最接近

[3] 有一個箱子容量為V（正整數(shù)，0≤V≤20000），同時有n個物品（0小于n≤30），每個物品有一個體積（正整數(shù)）。要求從n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。

2.2完全背包問題

（1）問題描述

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。

（2）狀態(tài)轉(zhuǎn)移方程

或者：

（3） 偽代碼

for i=1..N
 
  for v=0..V
 
    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍歷順序！??！

注意，時間復(fù)雜度仍為：O(VN).

（4） 舉例

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

計(jì)算順序是：從左往右，自上而下：

（2）背包剛好裝滿

計(jì)算順序是：從左往右，自上而下。注意初始值，其中-inf表示負(fù)無窮

（5） 經(jīng)典題型

[1] 找零錢問題：有n種面額的硬幣，每種硬幣無限多，至少用多少枚硬幣表示給定的面值M？

2.3多重背包問題

（1）問題描述

有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。

（2）狀態(tài)轉(zhuǎn)移方程

（3） 解題思想

用以下方法轉(zhuǎn)化為普通01背包問題：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個系數(shù)。使這些系數(shù)分別為 1,2,4,…,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種 物品分成系數(shù)分別為1,2,4,6的四件物品。這種方法能保證對于0..n[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示。這個很容易證明，證明過程中用到以下定理：任何一個整數(shù)n均可以表示成：n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(實(shí)際上就是n的二進(jìn)制分解)，

定理：一個正整數(shù)n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數(shù)）的形式，且1～n之內(nèi)的所有整數(shù)均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某幾個數(shù)的和的形式。

該定理的證明如下：

（1） 數(shù)列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的范圍為：[1, n]；

（2）如果正整數(shù)t<= 2^k – 1,則t一定能用1,2,4,…,2^(k-1)中某幾個數(shù)的和表示，這個很容易證明：我們把t的二進(jìn)制表示寫出來，很明顯，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二進(jìn)制數(shù)為0或者1.

（3）如果t>=2^k,設(shè)s=n-2^k+1，則t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某幾個數(shù)的和的形式，進(jìn)而t可以表示成1,2,4,…,2^(k-1)，s中某幾個數(shù)的和（加數(shù)中一定含有s）的形式。

（證畢！）

該算法的時間復(fù)雜度為：O(V*sum(logn[i])).

（4） 經(jīng)典題型

[1] 找零錢問題：有n種面額的硬幣，分別為a[0], a[1],…, a[n-1]，每種硬幣的個數(shù)為b[0], b[1],…, b[n-1]，至少用多少枚硬幣表示給定的面值M？

2.4二維費(fèi)用背包

（1）問題描述

二維費(fèi)用的背包問題是指：對于每件物品，具有兩種不同的費(fèi)用；選擇這件物品必須同時付出這兩種代價(jià)；對于每種代價(jià)都有一個可付出的最大值（背包容量）。問 怎樣選擇物品可以得到最大的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2，第i件物品所需的兩種代價(jià)分別為a[i]和b[i]。兩種代價(jià)可付出的最大值（兩種 背包容量）分別為V和U。物品的價(jià)值為w[i]。

（2）狀態(tài)轉(zhuǎn)移方程

（3）算法思想

采用同一維情況類似的方法求解

（4）經(jīng)典題型

有2n個整數(shù)，平均分成兩組，每組n個數(shù)，使這兩組數(shù)的和最接近。

3.背包總結(jié)

背包問題實(shí)際上代表的是線性規(guī)劃問題，一般要考慮以下幾個因素已決定選取什么樣的算法：

（1）約束條件，有一個還是兩個或者更多個，如果是一個，可能是01背包，完全背包或者多重背包問題，如果有兩個約束條件，則可能是二維背包問題。

（2）優(yōu)化目標(biāo)，求最大值，還是最小值，還是總數(shù)(只需將max換成sum)

（3）每種物品的個數(shù)限制，如果每種物品只有一個，只是簡單的01背包問題，如果個數(shù)無限制，則是完全背包問題，如果每種物品的個數(shù)有限制，則是多重背包問題。

（4）背包是否要求剛好塞滿，注意不塞滿和塞滿兩種情況下初始值不同。

4.參考資料

dd_engi：《背包問題九講》

最新評論