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

更新時(shí)間：2022年04月12日 12:07:24 作者：小羊努力變強(qiáng)

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

寫在前面

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

01背包問題

C語言數(shù)學(xué)問題與簡(jiǎn)單DP01背包問題詳解

先回憶一下這個(gè)圖

在這里插入圖片描述

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

在這里插入圖片描述

二維：

#include<bits/stdc++.h>

using namespace std;

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

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++)
        {
            //  當(dāng)前背包容量裝不進(jìn)第i個(gè)物品，則價(jià)值等于前i-1個(gè)物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能裝，需進(jìn)行決策是否選擇第i個(gè)物品
            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 ++ )//因?yàn)槊恳患锲范加袩o限件可用，我們只需要找出單件價(jià)值最高的商品就可以了
                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)系，那么其實(shí)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]);
}

這個(gè)代碼和01背包的非優(yōu)化寫法很像啊!!!我們對(duì)比一下，下面是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]);
}

兩個(gè)代碼其實(shí)只有一句不同（注意下標(biāo)）

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]);//完全背包問題

因?yàn)楹?1背包代碼很相像，我們很容易想到進(jìn)一步優(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++;
        }//將多重背包一個(gè)一個(gè)拆出來
    }

然后轉(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++;
        }//將多重背包一個(gè)一個(gè)拆出來
    }
    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)化就話超時(shí)，那怎么優(yōu)化呢？

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

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

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

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

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

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

一、二進(jìn)制與十進(jìn)制

普通遍歷問題

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

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

十進(jìn)制遍歷: 0,1,2,3,4,5,6,7 共 8 次遍歷

二進(jìn)制遍歷: 000, 001, 010, 011, 100, 101, 110, 111 共 8 次遍歷

多重背包問題

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

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

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

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

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

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

三、多重背包

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

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

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

十進(jìn)制遍歷方法

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

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

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

二進(jìn)制遍歷方法

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

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

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

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

最后請(qǐng)看代碼

#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 價(jià)值, s 每種物品的個(gè)數(shù)
        scanf("%d %d %d", &a, &b, &s);

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

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

    n = cnt;  // 所有的組數(shù)即為 01背包中的物品個(gè)數(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ù)：根據(jù)從第i組物品中選哪個(gè)物品進(jìn)行劃分.

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

請(qǐng)看代碼

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

const int N=110;
int f[N][N];  //只從前i組物品中選，當(dāng)前體積小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v為體積，w為價(jià)值，s代表第i組物品的個(gè)數(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;
}

因?yàn)橹挥玫搅说趇-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語言動(dòng)態(tài)規(guī)劃多種背包問題分析講解的文章就介紹到這了,更多相關(guān)C語言背包問題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: