01背包（動態規劃）小結

一，問題

【問題】

一個容量為m公斤的背包。現有n種物品，每種物品只有一件，它們的重量分別為w[ i ](1<=i<=n)，它們的價值分別為c[ i ](1<=i<=n)。求能放入背包的最大價值。

【輸入】

第一行：兩個整數，n(物品數量，n<51)和m(背包容量，m<201)。

第2，3，，，n+1行：每行兩個整數w[i],c[i],錶示每個物品的重量和價值。

【輸出】

一個數，錶示最大價值。

【樣例輸入】

3 6

3 5

2 3

4 6

【樣例輸出】

9

PS：

01背包：第 i 件物品可以放入0個或1個；

完全背包：第 i 件物品可以放入0個，1個，2個.........

二，解答思路

1，確定狀態變量（函數）；

2，確定狀態轉移方程（遞推關系）；

3，確定邊界條件。

最大價值是物品數量 i 和背包容量 j 的函數。

設函數 f[ i ][ j ] 錶示前 i 件物品放入容量為 j 的背包的最大價值。

最終的最大價值就是物品數量 i 從0增長到n，背包容量 j 從0增長到m時的 f[ n ][ m ] 的值。

 若當前背包容量為 j ，我們就要考慮第 i 件物品能否放入？是否放入？

1，當前背包容量 j<W[i], 不能放入，則 f[ i [ j ]=f[ i-1 ][ j ];

2，當前背包容量 j>=W[i]，能放入，但要比較價值：

（1）如果第 i 件物品不放入背包，則 f[ i ][ j ]=f[i-1][ j ];

（2）如果第 i 件物品放入背包，則f[ i ][ j ]=f[ i -1 ][ j-w[ i ] ]+c[ i ]

如果第 i 件物品放入背包，則背包容量還剩 j-w[ i ],所以要取前 i-1 件物品放入背包，剩餘容量 j-w[ i ]所獲得的最大價值為 f[ i-1 ][ j-w[i] ]。

舉個例子：

狀態轉移方程：

f[ i ][ j ]=f[ i-1 ][ j ],（j<w[ i ])

f[ i ][ j ]=max(f[ i-1 ][ j ],f[ i-1 ][ j-w[i] ]+c[ i ],(j>=w[ i ]) 

邊界條件：f[ i ][ j ]=0

三，代碼

for(i=1;i<=n;i++)//物品 i
{
    for(j=1;j<=m;j++)//容量 j
    {
        if(j<w[i])
            f[i][j]=f[i-1][j];
        else
            f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
    }
}
printf("%d",f[n][m]);

 

作進一步的優化：

 用一維數組 f[ j ] 只記錄一行數據。讓 j 值順序循環，順序更新 f[ j ] 的值。

最終簡化為：

for(i=1;i<=n;i++)//物品 i
{
    for(j=w[i];j<=m;j++)//容量 j
    {
        f[j]=max(f[j],f[j-w[i]]+c[i]);
    }
}
printf("%d",f[m]);

因為 j 是逆序循環，f[ j ]會先於 f[ j-w[i] ]更新，也就是說，用舊值 f[ j-w[i] ]去更新 f[ j ],相當於用上一行的 f[ j-w[i] ]去更新 f[ j ]。