動態規劃背包問題之完全背包詳解

上一篇我們學習了什麼是動態規劃問題和什麼是背包問題，並且分析了01背包，如果想看上一篇請轉移至–>背包問題之01背包詳解，今天我們來了解一下背包問題之完全背包問題.

一、什麼是完全背包問題？

有n種物品，每種物品的單件體積為v[i]，價值為w[i]。現有一個容量為V的背包，問如何選取物品放入背包，使得背包內物品的總價值最大。其中每種物品都有無窮件。
完全背包和01背包的區別：

1. 01背包在選擇某一個物品時只有不選和選一次兩種情况
2. 完全背包在選擇某一個物品時可以不選，也可以選一次，選兩次。。。選擇次數沒有上限（只要背包能放下）

二、例題分析

1. 題目：

2. 分析：

2.1 第一步：確定狀態變量（函數）

最大價值是物品數量i和背包容量j的函數。
設函數f[i][j]錶示前i件物品放入容量為j的背包的最大價值。
最終的最大價值就是物品數量i從0增長到n，背包容量j從0增長到m時的f[n][m]值。

2.2 第二步：確定狀態轉移方程

狀態變量：f[i][j]錶示前i件物品放入容量為j的背包的最大價值

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

1. 如果當前背包容量j<v[i],不能放入，則f[i][j]=f[i-1][j]
2. 如果當前背包容量j>=v[i]，能放入但是要比較代價
   2.1 如果第i件物品不放入背包，則f[i][j]=f[i-1][j]
   2.2 如果第i件物品放入背包，則f[i][j]=f[i][j-v[i]]+w[i]

對於前i件物品，背包容量為j-v[i]時可能已經放入了第i件物品，容量為j時還可以再放入第i件物品，所以用f[i][j-v[i]]更新f[i][j]

狀態轉移方程：

可以畫圖錶示為：

2.3 邊界條件

對於01背包來說邊界就是f[i][j]=0,即當i=0或者j=0時f[i][j]的值為0。

i=0時，錶示背包沒有放入一個物品，那麼此時背包的最大價值無從談起，所以為0；
j=0時，錶示背包的容量為0，那麼此時無法放入物品，所以最大價值也為0；

3. 過程錶示

3.1 核心代碼

    for(int i=1;i<=n;i++){
    //物品i
        for(int j=0;j<=m;j++)
            {
    
            if(j<v[i])
                f[i][j]=f[i-1][j];
             else
                f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
            }
     }
    cout<<f[n][m]<<endl;

3.2 手動計算

3.3 代碼驗證

3.4 完整代碼

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main ()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           {
    
               if(j<v[i])
                    f[i][j]=f[i-1][j];
                else
                    f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
           }
    cout<<f[n][m]<<endl;
    return 0;
}

3.5 優化

將二維錶示優化成一維，减少空間的使用，用一維數組f[j]只記錄一行數據，讓j值順序循環，順序更新f[j]
優化後的代碼

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main ()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           {
    
               if(j<v[i])
                    f[j]=f[j];
                else
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
           }
    cout<<f[m]<<endl;
    return 0;
}

因為j是順序循環，f[j-v[i]]會先於f[j]更新，也就是說，用新值f[j-v[i]]去更新f[j],相當於用第i行的f[j-v[i]]值更新f[j],所以正確。