1.背包問題介紹

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

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

2.背包問題及應用

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

2.101背包問題

（1）問題描述

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

（2）狀態轉移方程

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

（3） 偽代碼

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

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

注意v的遍歷順序！！！

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

（4） 舉例

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

（1）背包不一定裝滿

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

（2）背包剛好裝滿

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

（5） 經典題型

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

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

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

2.2完全背包問題

（1）問題描述

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

（2）狀態轉移方程

或者：

（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） 經典題型

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

2.3多重背包問題

（1）問題描述

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

（2）狀態轉移方程

（3） 解題思想

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

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

該定理的證明如下：

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

（2）如果正整數t<= 2^k

主站蜘蛛池模板： 久久r精品 | 国产精品成人3p一区二区三区 | 成年人在线视频免费观看 | 国产男女爽爽爽免费视频 | 伊人超碰 | 欧美日韩在线观看中文字幕 | 欧美激情综合色综合啪啪五月 | 欧美日韩在线一区二区 | 久久免费小视频 | 亚洲涩涩涩 | 一区二区日韩 | 男女羞羞视频在线免费观看 | 国产免费视频 | 女男羞羞视频网站免费 | 天天爽天天操 | 在线不卡视频 | 日本亚洲欧美 | 亚洲精品乱码久久久久久按摩观 | 日日夜夜天天 | 日韩av在线一区二区 | 好大好爽快点深一点陶软 | 久久成人激情视频 | 久久久一区二区 | 日日摸夜夜添夜夜添亚洲女人 | 污网站在线观看视频 | 国产精品美女久久久久图片 | 91免费看| 成人国产精品一级毛片视频 | 亚洲欧美一区二区三区久久 | 在线观看成人小视频 | 免费的黄色视屏 | 久久久久久美女 | 日韩国产欧美一区 | 日本在线精品 | 午夜免费电影 | 99精品欧美一区二区三区综合在线 | 欧美日韩国产高清 | 欧美日黄| 欧美一级做性受免费大片免费 | 久综合网 | 国产精品无码久久久久 |