關(guān)于背包問題的一些理解和應(yīng)用
更新時(shí)間：2014年08月28日 11:13:08 投稿：
這篇文章主要介紹了關(guān)于背包問題的一些理解和應(yīng)用,本文可以說是背包問題九講的補(bǔ)充、讀后感,需要的朋友可以參考下
1.背包問題介紹
背包問題不單單是一個(gè)簡單的算法問題，它本質(zhì)上代表了一大類問題，這類問題實(shí)際上是01線性規(guī)劃問題，其約束條件和目標(biāo)函數(shù)如下：
自從在2007年推出《背包問題九講》之后，背包問題的主要精髓基本已道盡。本文沒有嘗試對(duì)背包問題的本質(zhì)進(jìn)行擴(kuò)展或深入挖掘，而只是從有限的理解（這里指對(duì)《背包問題九講》的理解）出發(fā)，幫助讀者更快地學(xué)習(xí)《背包問題九講》中的提到的各種背包問題的主要算法思想，并通過實(shí)例解釋了相應(yīng)的算法，同時(shí)給出了幾個(gè)背包問題的經(jīng)典應(yīng)用。
2.背包問題及應(yīng)用
在《背包問題九講》中主要提到四種背包問題，分別為：01背包問題，完全背包問題，多重背包問題，二維費(fèi)用背包問題。本節(jié)總結(jié)了這幾種背包問題，并給出了其典型的應(yīng)用以幫助讀者理解這幾種問題的本質(zhì)。
2.101背包問題
（1）問題描述
有N件物品和一個(gè)容量為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時(shí)，f(i,v)初始化為0，表示題目不要求背包一定剛好裝滿，而f(i,v)=inf/-inf（正無窮或負(fù)無窮）表示題目要求背包一定要?jiǎng)偤醚b滿。下面幾種背包類似，以后不再贅述。
（3） 偽代碼
從轉(zhuǎn)移方程上可以看出，前i個(gè)物品的最優(yōu)解只依賴于前i-1個(gè)物品最優(yōu)解，而與前i-2，i-3,…各物品最優(yōu)無直接關(guān)系，可以利用這個(gè)特點(diǎn)優(yōu)化存儲(chǔ)空間，即只申請(qǐng)一個(gè)一維數(shù)組即可，算法時(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＜＝,N
[2] 給一個(gè)整數(shù)的集合，要把它分成兩個(gè)集合，要兩個(gè)集合的數(shù)的和最接近
[3] 有一個(gè)箱子容量為V（正整數(shù)，0≤V≤20000），同時(shí)有n個(gè)物品（0小于n≤30），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求從n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。
2.2完全背包問題
（1）問題描述
有N種物品和一個(gè)容量為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的遍歷順序?。。?/p>
注意，時(shí)間復(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種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。
（2）狀態(tài)轉(zhuǎn)移方程
（3） 解題思想
用以下方法轉(zhuǎn)化為普通01背包問題：將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(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的四件物品。這種方法能保證對(duì)于0..n[i]間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示。這個(gè)很容易證明，證明過程中用到以下定理：任何一個(gè)整數(shù)n均可以表示成：n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(實(shí)際上就是n的二進(jìn)制分解)，
定理：一個(gè)正整數(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中某幾個(gè)數(shù)的和的形式。
該定理的證明如下：
（1） 數(shù)列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的范圍為：[1, n]；
（2）如果正整數(shù)t=2^k,設(shè)s=n-2^k+1，則t-s
