1.背包問題介紹

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

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

2.背包問題及應用

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

2.101背包問題

（1）問題描述

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

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

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

（3） 偽代碼

從轉移方程上可以看出，前i個物品的最優(yōu)解只依賴于前i-1個物品最優(yōu)解，而與前i-2，i-3,…各物品最優(yōu)無直接關系，可以利用這個特點優(yōu)化存儲空間，即只申請一個一維數(shù)組即可，算法時間復雜度（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）背包不一定裝滿

計算順序是：從右往左，自上而下：

（2）背包剛好裝滿

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

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

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

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

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

2.2完全背包問題

（1）問題描述

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

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

或者：

（3） 偽代碼

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

注意v的遍歷順序！！！

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

（4） 舉例

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

（1）背包不一定裝滿

計算順序是：從左往右，自上而下：

（2）背包剛好裝滿

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

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

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

2.3多重背包問題

（1）問題描述

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

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

（3） 解題思想

用以下方法轉化為普通01背包問題：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(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(實際上就是n的二進制分解)，

定理：一個正整數(shù)n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數(shù)）的形式，且1～n之內的所有整數(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

主站蜘蛛池模板： 开封市| 剑川县| 丘北县| 西丰县| 吴桥县| 辛集市| 遂昌县| 都匀市| 东海县| 加查县| 海安县| 于都县| 麻栗坡县| 海门市| 安化县| 拉孜县| 乐陵市| 南漳县| 丰顺县| 华容县| 郑州市| 永泰县| 巩义市| 安图县| 平陆县| 清水河县| 友谊县| 响水县| 贡山| 宾川县| 湘潭县| 濮阳县| 邢台市| 平昌县| 长阳| 临清市| 永康市| 浦东新区| 晋中市| 延边| 德保县|