0-1背包問題
問題
n個(gè)物體，它們各自有重量和價(jià)值，給定一個(gè)有容量的背包希太，如何讓背包里裝入的物體價(jià)值總和最大？
例如：
物品數(shù)量：num=4酝蜒， 背包容量： capacity=8
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w(體積) | 2 | 3 | 4 | 5 |
| v(價(jià)值) | 3 | 4 | 5 | 6 |
原理
對于任意第 i 個(gè) 物品誊辉，只可能存在兩種可能: ①裝進(jìn)背包 or ②不裝進(jìn)背包。
在此之前先定義一些符號表示:
val(i, j) : 表示當(dāng)前背包可用空間為j亡脑，前i個(gè)物品最佳組合對應(yīng)的價(jià)值芥映。
因此，可以得到這么一個(gè)遞推關(guān)系式:
當(dāng)前物品裝不下远豺，j < w(i) val(i, j) = val (i - 1, j)
能裝下當(dāng)前物品，j >= w(i) val(i, j) = max { val(i - 1, j - w(i)) + v(i), val(i - 1, j) }
構(gòu)建表格
在理解了這個(gè)遞歸關(guān)系式后坞嘀，我們根據(jù)這個(gè)關(guān)系式來填寫如下的表格躯护，首先呢初始化邊界條件，即 val(0, j) = val (i, 0) = 0
這里舉幾個(gè)典型的栗子吧
比如說 val(2, 2), 此時(shí)背包容量j = 2丽涩，而i為2的背包重量w(2)為3棺滞，此時(shí)裝不下裁蚁，所以val(2, 2) = val (1, 2) = 3;
再舉個(gè)典型的例子，對于val(3, 4)继准，對于i= 3的背包枉证，w(3) = 4，而此時(shí)背包容量為4移必，能夠裝得下室谚，val(3, 4) =max { val(2, 4 - w(3)) + v(3), val(2, 4) } =max{ val(2, 0) + v(3), 4} = max{ 5, 4 } = 5;
就這樣，按著之前我們推到的遞推關(guān)系式來填寫表格即可崔泵。
這是整個(gè)建立這張表的過程實(shí)現(xiàn):
/**
* w[i] 第i個(gè)物品的重量
* v[i] 第i個(gè)物品的價(jià)值
*/
public void findMax() { //利用動(dòng)態(tài)規(guī)劃
for (int i = 1; i < num; i++) { // 開始填寫第 i 行秒赤，逐行填寫
for (int j = 1; j < capacity; j++) { // j 背包可裝載的容量
if (j < w[i]) { // 如果物品放不進(jìn)背包
val[i][j] = val[i - 1][j];
} else { // 能放進(jìn)背包
v[i][j] = Math.max(val[i - 1][j - w[i]] + v[i], val[i - 1][j]);
}
}
}
}
回溯找出背包方案
在構(gòu)建了表格后，我們已經(jīng)模擬了整個(gè)程序執(zhí)行的過程憎瘸，這個(gè)過程記錄了所有的步驟和相關(guān)信息入篮。而我們從表格中能夠得出的信息是，val(i ,j)的最大值其實(shí)就在val(4, 8)位置幌甘，也就是表格的最右下方潮售。我們還得知道這個(gè)最大值的選擇方案是什么，即我們的背包需要帶上哪幾個(gè)物品锅风？
這就是我們進(jìn)行回溯的意義了酥诽。
我們回溯的過程很簡單，相當(dāng)于從最后一個(gè)物品開始往回倒推遏弱，查看每一個(gè)物品是否被選擇盆均？
從最右下角的元素開始，對于每一個(gè)val(i, j) 漱逸，需要滿足以下規(guī)則:
① val(i , j) = val(i - 1, j) 泪姨，說明沒有選擇第i個(gè)物品，轉(zhuǎn)到val(i - 1, j)饰抒；
② val(i , j) ≠ val(i - 1, j)肮砾，則說明選擇了第i個(gè)物品，轉(zhuǎn)到val(i - 1, j - w[i]);
③ 重復(fù)以上步驟直到 i = 0 為止袋坑。
下面是回溯的實(shí)現(xiàn):
/**
* i , j 分別為第i個(gè)物品 和 背包剩余空間j
* res[i] 表示第i個(gè)物品是否被裝 仗处，取值→ 0 / 1
*/
public void traceBack(int i, int j) { // 回溯
if (i > 0) {
if (v[i][j] == v[i- 1][j]) { // 沒有裝此物品
res[i] = 0;
traceBack(i - 1, j);
} else {
res[i] = 1;
traceBack(i - 1, j - w[i]);
}
}
}
（未完待續(xù)）后面還將進(jìn)行一些其他背包問題的分析，盡量全面一點(diǎn)吧...
