寫在前
問題描述
若有 N 件物品和一個(gè)最多能裝重量為 W 的背包胰坟，一個(gè)物品只有兩個(gè)屬性：重量和價(jià)值。第i件物品的重量是weight[i]笔横，得到的價(jià)值是value[i] 。假設(shè)每件物品只能用一次商佑，將哪些物品裝入背包里物品價(jià)值總和最大厢塘？
注意：0-1 背包問題無法使用貪心算法來求解，也就是說礁叔，不能按照先添加性價(jià)比最高的物品來達(dá)到最優(yōu)迄薄，因?yàn)檫@種方式可能造成背包空間的浪費(fèi)，從而無法達(dá)到最優(yōu)。
基本思路
上述問題是典型的動(dòng)態(tài)規(guī)劃画机，這里有兩個(gè)可變量：重量和價(jià)值新症，我們定義dp[i][j]：前i件物品重量不超過j時(shí)背包能達(dá)到的最大價(jià)值徒爹，背包的初始狀態(tài)是最終目標(biāo)是dp[N][W]，即前N件物品重量不超過W時(shí)背包能達(dá)到的最大價(jià)值隆嗅。
設(shè)第 i 件物品重量為 w，價(jià)值為 v泡躯，根據(jù)第 i 件物品是否添加到背包中丽焊，可以分兩種情況討論：
- 第 i 件物品沒添加到背包，最大價(jià)值：
dp[i][j] = dp[i - 1][j]写穴。 - 第 i 件物品添加到背包中：
dp[i][j] = dp[i - 1][j - w] + v凫乖。
第 i 件物品可添加也可以不添加弓颈，取決于哪種情況下最大價(jià)值更大。因此导街，0-1 背包的狀態(tài)轉(zhuǎn)移方程為：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
代碼實(shí)現(xiàn)
// W 為背包總重量
// N 為物品數(shù)量
// weights 數(shù)組存儲(chǔ) N 個(gè)物品的重量
// values 數(shù)組存儲(chǔ) N 個(gè)物品的價(jià)值
public int knapsack(int W, int N, int[] weights, int[] values) {
// dp[i][0]和dp[0][j]沒有價(jià)值已經(jīng)初始化0
int[][] dp = new int[N + 1][W + 1];
// 從dp[1][1]開始遍歷填表
for (int i = 1; i <= N; ++i) {
// 第i件物品的重量和價(jià)值
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; ++j) {
if (w > j) {
// 超過當(dāng)前狀態(tài)能裝下的重量j
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
}
}
}
return dp[N][W];
}
由于dp[i][j]的值只與dp[i-1][0,...,j-1]有關(guān)纤子，可以采用動(dòng)態(tài)規(guī)劃常用的優(yōu)化方法（滾動(dòng)數(shù)組）對空間進(jìn)行優(yōu)化（即去掉dp的第一維）。因此泽论，0-1 背包的狀態(tài)轉(zhuǎn)移方程為： dp[j] = max(dp[j], dp[j - w] + v)
特別注意：為了防止上一層循環(huán)的dp[0,...,j-1]被覆蓋卡乾，循環(huán)的時(shí)候 j 只能逆向遍歷。優(yōu)化空間復(fù)雜度：
ps:滾動(dòng)數(shù)組：即讓數(shù)組滾動(dòng)起來鹦赎，每次都使用固定的幾個(gè)存儲(chǔ)空間，來達(dá)到壓縮古话，節(jié)省存儲(chǔ)空間的作用陪踩。
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; --j) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}
ps：01背包內(nèi)循環(huán)理解：還原成二維的dp就很好理解，一維的dp是二維dp在空間上進(jìn)行復(fù)用的結(jié)果肩狂。dp[i]=f(dp[i-num])，等式的右邊其實(shí)是二維dp上一行的數(shù)據(jù)描焰，應(yīng)該是只讀的栅螟，在被讀取前不應(yīng)該被修改。如果正序的話步绸，靠后的元素在讀取前右邊的dp有可能被修改了吃媒，倒序可以避免讀取前被修改的問題。
