問題描述
背包問題是一種組合優化的 np 完全問題：有 n 個物品和容量為 w 的背包，每個物品都有自己的體積 w 和價值 v，求拿哪些物品可以使得背包所裝下物品的總價值最大。如果限定每種物品隻能選擇 0 個或 1 個，則問題稱為 0-1 背包問題；如果不限定每種物品的數量，則問題稱為無界背包問題或完全背包問題。
輸入輸出樣例
輸入物品的數量，背包最大容量，每件物品的重量和價值，輸出背包所能裝下的物品最大價值。
input: 5
8
[3, 5, 2, 1, 4]
[4, 5, 3, 2, 2]
output: 10
輸出結果為10：當背包裝物品2，3，4時價值最大為10。
動态規劃：
我們可以用動态規劃來解決背包問題。動态規劃解法的關鍵是找到正确的狀态轉移方程：以 0-1 背包問題為例，我們可以定義一個二維數組 dp存儲最大價值，其中 dp[i][j] 表示前 i 件物品體積不超過 j 的情況下能達到的最大價值。在我們周遊到第 i 件物品時，在目前背包總容量為 j 的情況下，如果我們不将物品 i 放入背包，那麼動态規劃方程為：dp[i][j]= dp[i-1][j]，即前 i 個物品的最大價值等于隻取前 i-1 個物品時的最大價值；如果我們将物品 i 放入背包，假設第 i 件物品體積為 w，價值為 v，那麼我們得到動态規劃方程： dp[i][j] = dp[i-1][j-w] + v。我們隻需在周遊過程中對這兩種情況取最大值即可。
代碼：