日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：小羊努力變強 ? 更新時間： 2022-06-12 編程語言

寫在前面

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

01背包問題

C語言數學問題與簡單DP01背包問題詳解

先回憶一下這個圖

在這里插入圖片描述

在這我再將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;
}

原文鏈接：https://blog.csdn.net/qq_54847231/article/details/123850995

欄目分類
最近更新