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

0/1背包問題

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

特點：

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

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

解決方案：

動態(tài)規(guī)劃：這是解決0/1背包問題最常見的方法。通過構(gòu)建一個二維數(shù)組dp，其中dp[i] [j]表示考慮前i個物品，背包容量為j時的最大價值。狀態(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個物品，則背包容量減去該物品的重量，總價值加上該物品的價值；如果不選擇，則總價值不變。

已知w[]和v[]
int[][] dp = new int[n + 1][m + 1]for(int i = 1; i <= n; i++) {//遍歷物品，注意下標的對應(yīng)關(guān)系，這里都假設(shè)物品從下標1開始記錄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]);	}
}

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

我們現(xiàn)在設(shè)dp[j]是容量j時的最大價值，因為我們外層循環(huán)的i一直在自增，所以對于上一次的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])就萬事大吉了呢？寶貝你顯然是太天真了

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

如果有3個物品他們的花費和價值是

W: 1 2 3

V: 2 1 3

對于容量為5的背包

i=1時

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

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

i=1時

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

i=2時

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

i=3時

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

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

代碼如下：

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

還有個無傷大雅的小優(yōu)化，for(int j = m; j >= w[i]; j--), 因為你剩余的空間如果都放不下這個物體了，那這個物體的價值自然不會對答案產(chǎn)生影響，并且后續(xù)的遍歷中也不存在能放得下這個物體的情況，可以直接跳過

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

完全背包問題

問題描述： 與0/1背包問題類似，但每個物品可以無限次選擇。

特點：

• 每個物品可以被選擇多次。

解決方案：

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

代碼：

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