C語言動態(tài)規(guī)劃多種背包問題分析講解

更新時間：2022年04月12日 12:07:24 作者：小羊努力變強

背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高

寫在前面

之前講過簡單DP，經(jīng)典01背包問題，在這我將會把背包問題更深入的講解，希望能幫助大家更好的理解。

01背包問題

C語言數(shù)學問題與簡單DP01背包問題詳解

先回憶一下這個圖

在這里插入圖片描述

在這我再將01背包問題代碼發(fā)一遍，可以用來做對比。

在這里插入圖片描述

二維：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 體積
int w[MAXN];    // 價值 
int f[MAXN][MAXN];  // f[i][j], j體積下前i個物品的最大價值 

int main() 
{
    int n, m;   
    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++)
        {
            //  當前背包容量裝不進第i個物品，則價值等于前i-1個物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能裝，需進行決策是否選擇第i個物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

一維：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

int main() 
{
    int n, m;   
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;      // 邊輸入邊處理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

完全背包問題

在這里插入圖片描述

完全背包問題和01背包問題的區(qū)別就在于完全背包問題中每件物品都有無限件可用。我們也可以先來試一下暴力寫法。

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int dp[N][N], v[N], w[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 = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )//因為每一件物品都有無限件可用，我們只需要找出單件價值最高的商品就可以了
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
    cout << dp[n][m] << endl;
}

優(yōu)化思路：

我們列舉一下更新次序的內(nèi)部關(guān)系：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)

f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , …)

由上兩式，可得出如下遞推關(guān)系：

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

有了上面的關(guān)系，那么其實k循環(huán)可以不要了，核心代碼優(yōu)化成這樣：

for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
    f[i][j] = f[i-1][j];
    if(j-v[i]>=0)
        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}

這個代碼和01背包的非優(yōu)化寫法很像啊!!!我們對比一下，下面是01背包的核心代碼

for(int i = 1 ; i <= n ; i++)
for(int j = 0 ; j <= m ; j ++)
{
    f[i][j] = f[i-1][j];
    if(j-v[i]>=0)
        f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}

兩個代碼其實只有一句不同（注意下標）

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包問題

因為和01背包代碼很相像，我們很容易想到進一步優(yōu)化。核心代碼可以改成下面這樣

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，這里的j是從小到大枚舉，和01背包不一樣
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }

綜上所述，完全背包的最終寫法如下：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    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 = v[i] ; j<=m ;j++)
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}

多重背包問題 I

在這里插入圖片描述

我們先來看這多重背包問題和01背包問題是不是很像，將s×v，s×w是不是就可以看成01背包問題了？

for(ll i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        for(ll j=1;j<=c;j++)
        {
            v[cnt]=a;
            w[cnt]=b;
            cnt++;
        }//將多重背包一個一個拆出來
    }

然后轉(zhuǎn)換成01背包問題解決。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=1e5+100;

ll v[N],w[N];
ll f[N];
int main()
{
    ll n,m;
    ll cnt=1;
    cin>>n>>m;
    ll a,b,c;
    for(ll i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        for(ll j=1;j<=c;j++)
        {
            v[cnt]=a;
            w[cnt]=b;
            cnt++;
        }//將多重背包一個一個拆出來
    }
    for(ll i=1;i<=cnt;i++)
    {
        for(ll j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }//01背包
    cout<<f[m];
    return 0;
}

多重背包問題 II

在這里插入圖片描述

這道題和1看起來沒什么區(qū)別，但是數(shù)據(jù)范圍變了，數(shù)據(jù)范圍變了如果不優(yōu)化就話超時，那怎么優(yōu)化呢？

我們只需要將轉(zhuǎn)換成01背包問題那一部分優(yōu)化了就可以了。

int cnt = 0;     // 將物品重新分組后的順序
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;    // a 體積, b 價值, s 每種物品的個數(shù)
        scanf("%d %d %d", &a, &b, &s);

        int k = 1;   // 二進制拆分 打包時每組中有 k 個同種物品
        while (k <= s)  // 即y總說的: 最后一組的物品個數(shù) < 2^(n+1)   1 2 4 8 16 ... 2^n 2^(n+1)
        {
            cnt ++;
            v[cnt] = a * k;  // 每組的體積
            w[cnt] = b * k;  // 每組的價值
            s -= k;
            k *= 2;  // 注意是 k * 2，每次增長一倍，不是k * k
        }

        if (s > 0)   // 二進制拆分完之后 剩下的物品個數(shù)分為新的一組
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

為什么可以這樣優(yōu)化呢

我們知道任何一個數(shù)都可以轉(zhuǎn)化成二進制的數(shù)，那二進制和十進制的區(qū)別在哪呢?

一、二進制與十進制

普通遍歷問題

遍歷 n 個物品, 采用二進制計數(shù)方法遍歷與采用十進制技術(shù)方法遍歷的時間復(fù)雜度是一樣的

舉例來說, 對于十進制數(shù) 8

十進制遍歷: 0,1,2,3,4,5,6,7 共 8 次遍歷

二進制遍歷: 000, 001, 010, 011, 100, 101, 110, 111 共 8 次遍歷

多重背包問題

同樣的道理, 對于多重背包問題, 采用二進制的遍歷方法不能優(yōu)化時間復(fù)雜度

優(yōu)化的原因在于引入了動態(tài)規(guī)劃

二、動態(tài)規(guī)劃的時間復(fù)雜度估算

動態(tài)規(guī)劃的時間復(fù)雜度 ≈≈ 問題的總個數(shù) × 問題要做出的選擇數(shù)

如, 對于 01 背包問題, 問題的總個數(shù)為N⋅V (N 為物品個數(shù), V 為背包容量), 問題要做出的選擇數(shù)為 2(選或不選)

則 01 背包問題的時間復(fù)雜度約為 2N⋅V

三、多重背包

如果不采用動態(tài)規(guī)劃的做法, 就像普通的遍歷問題那樣, 是否采用二進制的計數(shù)方法對時間復(fù)雜度的優(yōu)化沒有任何關(guān)系

但采用二進制的計數(shù)方法會影響問題的總個數(shù)與問題的選擇數(shù)的乘積, 即動態(tài)規(guī)劃做法下多重背包的時間復(fù)雜度

多重背包的動態(tài)規(guī)劃時間復(fù)雜度

十進制遍歷方法

問題的總個數(shù)為 N⋅V, N 為物品的種類數(shù), V 為背包容量

問題的選擇數(shù)約為 Smax,Smax 為每種物品數(shù)量的最大值

十進制下多重背包問題的 DP 時間復(fù)雜度為: N⋅V⋅Smax

二進制遍歷方法

十進制下, 一種物品有 si個, 二進制下, 變?yōu)?1, 2, … , lgsi 個物品, 則共有 lgs1+lgs2+…+lg?sn 個物品, 約為 Nlgsmax 個物品

問題的總個數(shù)為 N⋅V⋅lgsmax

問題的選擇數(shù)為 2

十進制下多重背包問題的 DP 時間復(fù)雜度為: 2N⋅V⋅lgsmax

最后請看代碼

#include <bits/stdc++.h>

using namespace std;

const int N = 11 * 1000 + 10, M = 2010;

int v[N], w[N];
int f[M];

int main()
{
    int  n, m;
    scanf("%d %d", &n, &m);

    int cnt = 0;     // 將物品重新分組后的順序
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;    // a 體積, b 價值, s 每種物品的個數(shù)
        scanf("%d %d %d", &a, &b, &s);

        int k = 1;   // 二進制拆分 打包時每組中有 k 個同種物品
        while (k <= s)  // 即y總說的: 最后一組的物品個數(shù) < 2^(n+1)   1 2 4 8 16 ... 2^n 2^(n+1)
        {
            cnt ++;
            v[cnt] = a * k;  // 每組的體積
            w[cnt] = b * k;  // 每組的價值
            s -= k;
            k *= 2;  // 注意是 k * 2，每次增長一倍，不是k * k
        }

        if (s > 0)   // 二進制拆分完之后 剩下的物品個數(shù)分為新的一組
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;  // 所有的組數(shù)即為 01背包中的物品個數(shù)

    // 寫01背包模板
    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d", f[m]);

    return 0;
}

分組背包問題

在這里插入圖片描述

狀態(tài)表示：f[i][j]

集合：從前i組物品中選,且總體積不超過j的所有方案的集合.

屬性：最大值

狀態(tài)計算：

思想-----集合的劃分

集合劃分依據(jù)：根據(jù)從第i組物品中選哪個物品進行劃分.

f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

請看代碼

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N][N];  //只從前i組物品中選，當前體積小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v為體積，w為價值，s代表第i組物品的個數(shù)
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];  //讀入
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];  //不選 不選表示不選第 i 組物品的所有物品，只從前 i?1 組物品里面選
            for(int k=0;k<s[i];k++){
                if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[n][m]<<endl;
}

因為只用到了第i-1列，所以可以仿照01背包的套路逆向枚舉體積

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=0;i<n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以
                if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[m]<<endl;
}

到此這篇關(guān)于C語言動態(tài)規(guī)劃多種背包問題分析講解的文章就介紹到這了,更多相關(guān)C語言背包問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: