C語言動態規劃多種揹包問題分析講解

2022-04-12 13:00:11

寫在前面

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

01揹包問題

先回憶一下這個圖

在這我再將01揹包問題程式碼發一遍，可以用來做對比。

二維：

#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揹包問題的區別就在於完全揹包問題中每件物品都有無限件可用。我們也可以先來試一下暴力寫法。

#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;
}

優化思路：

我們列舉一下更新次序的內部關係：

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 , …)

由上兩式，可得出如下遞推關係：

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

有了上面的關係，那麼其實k迴圈可以不要了，核心程式碼優化成這樣：

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揹包的非優化寫法很像啊!!!我們對比一下，下面是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揹包程式碼很相像，我們很容易想到進一步優化。核心程式碼可以改成下面這樣

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++;
        }//將多重揹包一個一個拆出來
    }

然後轉換成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看起來沒什麼區別，但是資料範圍變了，資料範圍變了如果不優化就話超時，那怎麼優化呢？

我們只需要將轉換成01揹包問題那一部分優化了就可以了。

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

        int k = 1;   // 二進位制拆分 打包時每組中有 k 個同種物品
        while (k <= s)  // 即y總說的: 最後一組的物品個數 < 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)   // 二進位制拆分完之後 剩下的物品個數分為新的一組
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

為什麼可以這樣優化呢

我們知道任何一個數都可以轉化成二進位制的數，那二進位制和十進位制的區別在哪呢?

一、二進位制與十進位制

普通遍歷問題

遍歷 n 個物品, 採用二進位制計數方法遍歷與採用十進位制技術方法遍歷的時間複雜度是一樣的

舉例來說, 對於十進位制數 8

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

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

多重揹包問題

同樣的道理, 對於多重揹包問題, 採用二進位制的遍歷方法不能優化時間複雜度

優化的原因在於引入了動態規劃

二、動態規劃的時間複雜度估算

動態規劃的時間複雜度 ≈≈ 問題的總個數 × 問題要做出的選擇數

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

則 01 揹包問題的時間複雜度約為 2N⋅V

三、多重揹包

如果不採用動態規劃的做法, 就像普通的遍歷問題那樣, 是否採用二進位制的計數方法對時間複雜度的優化沒有任何關係

但採用二進位制的計數方法會影響問題的總個數與問題的選擇數的乘積, 即動態規劃做法下多重揹包的時間複雜度

多重揹包的動態規劃時間複雜度

十進位制遍歷方法

問題的總個數為 N⋅V, N 為物品的種類數, V 為揹包容量

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

十進位制下多重揹包問題的 DP 時間複雜度為: N⋅V⋅Smax

二進位制遍歷方法

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

問題的總個數為 N⋅V⋅lgsmax

問題的選擇數為 2

十進位制下多重揹包問題的 DP 時間複雜度為: 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 每種物品的個數
        scanf("%d %d %d", &a, &b, &s);

        int k = 1;   // 二進位制拆分 打包時每組中有 k 個同種物品
        while (k <= s)  // 即y總說的: 最後一組的物品個數 < 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)   // 二進位制拆分完之後 剩下的物品個數分為新的一組
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;  // 所有的組數即為 01揹包中的物品個數

    // 寫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;
}

分組揹包問題

狀態表示：f[i][j]

集合：從前i組物品中選,且總體積不超過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組物品的個數
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;
}

到此這篇關於C語言動態規劃多種揹包問題分析講解的文章就介紹到這了,更多相關C語言揹包問題內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言動態規劃多種揹包問題分析講解

目錄

寫在前面

01揹包問題

完全揹包問題

多重揹包問題 I

多重揹包問題 II

為什麼可以這樣優化呢

一、二進位制與十進位制

二、動態規劃的時間複雜度估算

三、多重揹包

分組揹包問題

熱門文章

C語言動態規劃多種揹包問題分析講解

目錄

寫在前面

01揹包問題

完全揹包問題

多重揹包問題 I

多重揹包問題 II

為什麼可以這樣優化呢

一 、二進位制與十進位制

二 、動態規劃的時間複雜度估算

三 、多重揹包

分組揹包問題

熱門文章

一、二進位制與十進位制

二、動態規劃的時間複雜度估算

三、多重揹包