背包演算法動態規劃

❶ 用動態規劃演算法怎樣求解01背包問題

動態規劃主要解決的是多階段的決策問題。

01背包中，狀態為背包剩餘的容量，階段是每一個物品，決策是是否選擇當前的物品。

所以用動態規劃來解決是非常貼切的。

我們設f[V]表示已經使用容量為V時所能獲得的最大價值，w[i]表示i物品的質量，c[i]表示i物品的價值。

for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);

這便是所謂的一個狀態轉移方程。

f[j]表示在已經使用容量為j時的最大價值，f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。

f[j]可以由f[j-w[i]]這個狀態轉移到達，表示選取w[i]這個物品，並從而獲得價值為c[i]。

而每次f[j]會在選與不選中決策選出最優的方案。

從每一個物品，也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題