當前位置:網站首頁>01背包(動態規劃)小結

01背包(動態規劃)小結

2022-01-27 17:10:38 別搶我的辣條~

一,問題

問題】

一個容量為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 ]。

版權聲明
本文為[別搶我的辣條~]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271710382382.html

隨機推薦