背包問(wèn)題是一種組合優(yōu)化的問(wèn)題，它有多種變體，但最常見(jiàn)的兩種是0/1背包問(wèn)題和完全背包問(wèn)題。

0/1背包問(wèn)題

問(wèn)題描述： 假設(shè)你有一個(gè)背包，背包的容量為W（可以是重量或者體積等度量），同時(shí)有n個(gè)物品，每個(gè)物品都有自己的重量w[i]和價(jià)值v[i]?，F(xiàn)在的目標(biāo)是選擇一些物品放入背包，使得背包中物品的總價(jià)值最大，但背包的總重量不能超過(guò)W。

特點(diǎn)：

• 每個(gè)物品只能選擇一次，即不能分割。

• 選擇放入背包或者不放入背包。

解決方案：

動(dòng)態(tài)規(guī)劃：這是解決0/1背包問(wèn)題最常見(jiàn)的方法。通過(guò)構(gòu)建一個(gè)二維數(shù)組dp，其中dp[i] [j]表示考慮前i個(gè)物品，背包容量為j時(shí)的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程為： dp[i] [j]=max?(dp[i?1] [j],dp[i?1] [j?w[i]]+v[i]), dp[i] [j]=max(dp[i?1] [j],dp[i?1] [j?w[i]]+v[i]) 其中，如果選擇第i個(gè)物品，則背包容量減去該物品的重量，總價(jià)值加上該物品的價(jià)值；如果不選擇，則總價(jià)值不變。

已知w[]和v[]
int[][] dp = new int[n + 1][m + 1]for(int i = 1; i <= n; i++) {//遍歷物品，注意下標(biāo)的對(duì)應(yīng)關(guān)系，這里都假設(shè)物品從下標(biāo)1開(kāi)始記錄for(int j = 1; j <= m; j++) {//遍歷容量if(j >= w[i])dp[i][j] = Math.max(d[i-1][j], dp[i-1][j-w[i]] + v[i]);	}
}

但是我們觀察動(dòng)態(tài)規(guī)劃方程發(fā)現(xiàn)：對(duì)于考慮前i個(gè)物品的時(shí)候我們只需要用到i-1這一個(gè)狀態(tài)，所以我們能不能將二維的數(shù)組壓縮成一維的呢？答案顯然是可以的

我們現(xiàn)在設(shè)dp[j]是容量j時(shí)的最大價(jià)值，因?yàn)槲覀兺鈱友h(huán)的i一直在自增，所以對(duì)于上一次的dp[j]就相當(dāng)與dp[i-1] [j], 所以我們只要不斷更新dp[j]就行。那是否是在上述代碼的基礎(chǔ)上將遞推方程由 dp[i] [j]=max?(dp[i?1] [j],dp[i?1] [j?w[i]]+v[i])改為dp[j] = max(dp[j], dp[j-w[i]] + v[i])就萬(wàn)事大吉了呢？寶貝你顯然是太天真了

我們?cè)賮?lái)捋一下，如果我們用for(int j = 1; j <= m; j++)，我們每次更新都是從低位開(kāi)始的，并且后續(xù)的遞推要用到前面的結(jié)論，那我們來(lái)舉例一下：

如果有3個(gè)物品他們的花費(fèi)和價(jià)值是

W: 1 2 3

V: 2 1 3

對(duì)于容量為5的背包

i=1時(shí)

dp[1]=2, dp[2] = 4, dp[3] = 6, dp[4] = 8, dp[5] = 10 有沒(méi)有發(fā)現(xiàn)端倪為毛我這次的修改全體現(xiàn)到之后的更新上了這不對(duì)吧，按我們的設(shè)想因該是i=2的那次才會(huì)應(yīng)用上才對(duì)（但是這在完全背包問(wèn)題中會(huì)被用到）

我們換倒序一下for(int j = m; j > 0; j--)

i=1時(shí)

dp[5] = 2, dp[4] = 2, dp[3] = 2, dp[2] = 2, dp[1] = 2;

i=2時(shí)

dp[5] = 3, dp[4] = 3, d[3] = 3, dp[2] = 2, dp[1] = 2

i=3時(shí)

dp[5] = 5, dp[4] = 5, d[3] = 3, dp[2] = 2, dp[1] = 2

這不就全對(duì)上了嘛，所以倒序可以避免這次的修改影響這次其它容量時(shí)的更新

代碼如下：

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍歷物品，注意下標(biāo)的對(duì)應(yīng)關(guān)系，這里都假設(shè)物品從下標(biāo)1開(kāi)始記錄for(int j = m; j > 0; j--) {//遍歷容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}

還有個(gè)無(wú)傷大雅的小優(yōu)化，for(int j = m; j >= w[i]; j--), 因?yàn)槟闶Ｓ嗟目臻g如果都放不下這個(gè)物體了，那這個(gè)物體的價(jià)值自然不會(huì)對(duì)答案產(chǎn)生影響，并且后續(xù)的遍歷中也不存在能放得下這個(gè)物體的情況，可以直接跳過(guò)

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍歷物品，注意下標(biāo)的對(duì)應(yīng)關(guān)系，這里都假設(shè)物品從下標(biāo)1開(kāi)始記錄for(int j = m; j >= w[i]; j--) {//遍歷容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}

完全背包問(wèn)題

問(wèn)題描述： 與0/1背包問(wèn)題類似，但每個(gè)物品可以無(wú)限次選擇。

特點(diǎn)：

• 每個(gè)物品可以被選擇多次。

解決方案：

• 動(dòng)態(tài)規(guī)劃：同樣使用動(dòng)態(tài)規(guī)劃，但是狀態(tài)轉(zhuǎn)移方程有所不同，因?yàn)槲锲房梢员恢貜?fù)選擇： dp[j]=max?(dp[j],dp[j?w[i]]+v[i]) , dp[j]=max?(dp[j],dp[j?w[i]]+v[i])其中，對(duì)于每個(gè)物品，我們嘗試多次放入背包，直到背包容量不足以再放入該物品為止。

代碼：

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍歷物品，注意下標(biāo)的對(duì)應(yīng)關(guān)系，這里都假設(shè)物品從下標(biāo)1開(kāi)始記錄for(int j = 1; j <= w; j++) {//遍歷容量if(j >= w[i])dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}