一 問題描述
現(xiàn)有n件物品和一個(gè)容量為c的背包秃诵。第i件物品的重量是重量為w[i]，價(jià)值是v[i]帐我。已知對(duì)于一件物品必須選擇瓤擦丁（用1表示）或者不取（用0表示）拦键，且每件物品只能被取一次（這就是“0-1”的含義）谣光。求放置哪些物品進(jìn)背包，可使這些物品的重量總和不超過背包容量芬为，且價(jià)值總和最大萄金。
二 算法要點(diǎn)分析
對(duì)于上述問題，如果使用暴力求解的方式來編程媚朦，共n件物品氧敢，每個(gè)物品的狀態(tài)為選取或者不選，算法復(fù)雜度為O(2n)询张。隨著n的不斷增加孙乖，算法運(yùn)行時(shí)間將呈指數(shù)級(jí)增長，所以需要找到復(fù)雜度更低的算法來解決上述問題，而動(dòng)態(tài)規(guī)劃即是最為常見的上述問題的高效解決方法唯袄。拋磚引玉弯屈，如有錯(cuò)誤請(qǐng)不吝賜教。
本著不做無用創(chuàng)新的原則恋拷，偷懶選取大多相關(guān)博客中所使用的例子资厉。 假設(shè)有5件物品，其重量分別是w={2蔬顾，2宴偿，6，5诀豁，4}酪我，價(jià)值分別是v={6，3且叁，5都哭，4，6}逞带，背包容量為10欺矫。在數(shù)學(xué)問題中這是典型的線性規(guī)劃問題，我們可以在線性約束范圍內(nèi)求解目標(biāo)表達(dá)式展氓。但是怎么用計(jì)算機(jī)語言實(shí)現(xiàn)呢穆趴？
***算法推演關(guān)系描述
我們用一個(gè)二維數(shù)組 m [ ] [ ]來記錄在某個(gè)背包容量下，某個(gè)物品數(shù)下所對(duì)應(yīng)的最大包內(nèi)價(jià)值遇汞，我們可以想象這樣一種遞推關(guān)系：
當(dāng)背包容量為 j 未妹，物品數(shù)為1時(shí)，此時(shí)所能裝下的最大價(jià)值的物品就是裝此物品的包內(nèi)總價(jià)值和不裝（放不下）此物品的包內(nèi)總價(jià)值的最大值（似乎顯而易見空入，而此算法的核心思想就在于此）, 此最大值即為m[ 1 ][ j ] 络它；
我們將物品數(shù)增加1氓奈，變?yōu)?個(gè)物品,第二個(gè)物品的重量為 w [2],價(jià)值為v [2]尿这，而此時(shí)所能裝下的最大價(jià)值的物品就是裝此物品的包內(nèi)總價(jià)值和不裝此物品的包內(nèi)總價(jià)值的最大值(不用對(duì)比兩句話了辉词，核心思想是不變的)合瓢，對(duì)應(yīng)的遞推公式就是m[ 2 ][ j ] = max( m[ 1 ] [ j - w[ 2 ] ] + v [ 2 ] ,m[ 1 ][ j ] )。max函數(shù)中的左項(xiàng)為當(dāng)物品數(shù)為1狐蜕，背包容量為 j 減去第二個(gè)物品重量時(shí)所能裝下的最大價(jià)值糖儡，然后再加上第二個(gè)物品的價(jià)值悴品，即先默認(rèn)肯定裝第二個(gè)物品白对。相似的max函數(shù)中的右項(xiàng)為當(dāng)不裝第二件商品掠廓，背包容量為j，物品數(shù)為1時(shí)所能裝下的最大價(jià)值甩恼。
一般化蟀瞧，將上述遞推關(guān)系1 至 2推廣到 i 至 i+1仍然成立狰域，綜上得出一般化遞推公式為（i = 0表示放入1件商品,依次類推）：
（1）i=0
當(dāng) j < w [0] 時(shí)，m [0] [j] =0黄橘；
當(dāng)j >= w[0]時(shí)，m[0][j]=v[0]
（2）i>0
當(dāng)j < w [i]屈溉，m [i] [j] = m [i-1] [j]塞关；
當(dāng)j >= w[i]，m [i] [j] = max{ m[i-1][j-w[i]]+v[i] 子巾，m[i-1][j] }
三 完整函數(shù)代碼
import java.util.Scanner;
public class Package01 {
int n;// 表示物品的數(shù)量
int m;// 表示背包的最大重量
int[] w; // 表示每一個(gè)物品的重量
int[] v; // 表示每一個(gè)物品的價(jià)值
int[][] f; // 用來表示狀態(tài)轉(zhuǎn)移方程
public void sovle() {
// 初始化各初始條件
init();
// 首先構(gòu)造第一行上
int i = 0, j = 0;
for (j = 1; j <= m; j++) {
if (j < w[i]) {
f[i][j] = 0;
} else {
f[i][j] = v[i];
}
}
// 然后對(duì)剩下的n-1個(gè)物品填充
for (i = 1; i < n; i++) {
for (j = 1; j <= m; j++) {
if (j < w[i]) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = Math.max(f[i - 1][j - w[i]] + v[i], f[i - 1][j]);
}
}
}
// 輸出打印地推二維表
for (i = 0; i < n; i++) {
for (j = 1; j <= m; j++) {
System.out.print(f[i][j] + "\t");
}
System.out.println();
}
}
public void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();// 初始化物品的數(shù)量
m = sc.nextInt();// 初始化背包的最大重量
w = new int[n];
v = new int[n];
f = new int[n][m + 1]; // 初始化狀態(tài)轉(zhuǎn)移方程
// 初始化每個(gè)物品重量
for (int i = 0; i < n; i++) {
w[i] = sc.nextInt();
}
// 初始化每個(gè)物品的價(jià)值
for (int i = 0; i < n; i++) {
v[i] = sc.nextInt();
}
sc.close();
}
public static void main(String[] args) {
new Package01().sovle();
}
}
四 復(fù)雜度
顯然算法空間復(fù)雜度與時(shí)間復(fù)雜度均為O(n*m)帆赢。其中m為背包容量。
五 總結(jié)
用動(dòng)態(tài)規(guī)劃算法解決0-1背包問題相較于暴力求解法時(shí)間復(fù)雜度大大降低线梗，理解關(guān)鍵在于狀態(tài)轉(zhuǎn)移方程的推演過程椰于。
