當前位置:網站首頁>動態規劃背包問題之完全背包詳解

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

2022-07-23 16:30:51四舍五入兩米高的小晨

上一篇我們學習了什麼是動態規劃問題和什麼是背包問題,並且分析了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],所以正確。

版權聲明
本文為[四舍五入兩米高的小晨]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207231229588777.html

隨機推薦