如何理解背包問題

本篇內容主要講解“如何理解背包問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“如何理解背包問題”吧!

0-1背包問題的二維bc

#include <iostream>
#include <cstring>
#include <cstdio>
#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];
    //當選擇0件物品時，價值總和為0，即f[0][0~m] = 0;
    //由于已定義為全局變量，已經初始化為0，所以可以不寫了。
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            //不選擇第i個物品的方案
            f[i][j]=f[i-1][j];
            //選擇第i個物品的方案可能不存在
            //選擇第i個物品————先去掉第i個物品，減去其重量再加上其價值。
            if(j>=v[i]){
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

優化（轉換成一維，滾動數組）

#include <iostream>
#include <cstring>
#include <cstdio>
#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=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

到此，相信大家對“如何理解背包問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！