1樓：朱星滔
先不管獲得最大價值的方案是啥， 直接考慮最後一步 ，反正是從n個物品裡面選，最後乙個裝的物品可能是第1個，第2個，也可能是第n個，甚至可能乙個都裝不下。
假設最後乙個裝的物品是第i個，對於體積為j的揹包 ，如果體積j >=v[i], 才能把物品裝進來，
那麼怎麼用程式語言描述呢？ if (j >= v[i]) f[i][j] = max（f[i-1][j-v[i]] + w[i], f[i-1][j])
為啥要max呢？因為對於最大值的那種方案，最後乙個物品我們不知道到底裝不裝進揹包
1.如果裝了最後乙個物品v[i],並且j足夠大能容納v[i]，價值相當於 f[i-1][j-v[i]] + w[i]
2.如果不裝最後乙個物品,價值就相當於前i-1個物品用j的體積的揹包能夠產生的最大值，即f[i-1][j]
對於最後一步f[i][j] ，最大值就是這兩者裡面的最大值（因為最後乙個物品要麼裝，要麼不裝，兩種情形的最大值都已經算出來了，取個max即可)。
其實最後的答案是max(f[n][0],f[n][1],....f[n][m]), 但是你揹包容量越大，產生的價值必然比揹包容量小時能獲取的價值大，至少會等於。所以直接f[n][m]
f[i][j]表示前i個物品，用j的體積的揹包去裝產生的最大價值
怎麼求呢？ 就是列舉前 i個物品。
1. 先計算出對於第乙個物品，用體積 j = 0 ~ m之間的值，能產生的最大價值。
2.再看第二個物品，用體積j=0~m之前的值，去看能產生的最大價值。
由於要考慮前一件物品的影響，所以就用f[i-1][j-v[i]]嘍，我們在i-1輪迴圈時,把各種體積裝前乙個物品產生的最大價值都算出來了，可以用於輔助到當前輪次的計算。 以此類推。
動態規劃就是利用前面的值來輔助處理後面
能否講講你對01揹包問題的理解？
每天一罐黑瓶紅牛 小白嘗試解答一下。揹包問題給我的感覺就是，看了答案好像挺明白，可一細琢磨，就暈了。我在這裡給出我的一種解釋。假設 我會一種魔法，這種魔法能夠幫我進行最優選擇。我不需要知道魔法原理。V i j 我只考慮前i個物品。當容量為j時，我使用魔法，魔法進行最優選擇，從中選出某些物品，使得包裹...
物體體積和價值正相關的01揹包問題有什麼好的解法麼？
題主應該好好看看knapsack這本書。線性01規劃問題已經被研究的非常成熟了。semidefinite relaxation,lagrangian relaxation效果都不錯啊。但天下沒有免費的午餐，每個具體問題都需要仔細推理驗證，這才是重點。 花落憶流年 貪婪演算法通常用單位體積的價值來衡量...
動態規劃能得到一類問題的最優解，比如揹包問題用動態規劃來解決，如何證明這個解就是相對應問題的最優解呢？
Tanki Zhang 先回顧下動態規劃問題的求解過程 1 證明該問題具有最優子結構性質 區域性最優解能決定全域性最優解 2 根據最優子結構，求遞推方程 3 根據遞推方程，說明該問題具有重疊子結構性質 4 自底向上寫出求解最優值的非遞迴演算法，同時構造最優解的解空間樹 5 遍歷解空間樹，求得最優解。...