背包知识汇总

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

背包知识汇总

作者：

梦念小袁 , 2024-10-15 17:11:14 , 所有人可见 , 阅读 8

1.01背包

时间复杂度$(n*m) 空间复杂度(m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N],dp[N];

int n,m;
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--)
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);

    cout << dp[m] << endl;

    return 0;
}

如果是恰好装满就需要让一些状态不可抵达
时间复杂度$(n*m) 空间复杂度(m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int v[N],w[N];
int dp[N];

int n,m;

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    memset(dp,0xcf,sizeof dp);
    dp[0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

记录在最优解的时候选择了哪些物品
时间复杂度$(n*m) 空间复杂度(n*m)$

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N],w[N],v[N];
int n,m;
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++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }

    int k=m;

    // 由于是一个一个加入的 也就是我们需要倒着来把这些东西吐出来

    // 如果我吐出来依旧符合那就是可以选择的因为前面的是已经抵达的合理状态
    for(int i=n;i>=1;i--)
        if(k>=v[i] && f[i][k]==f[i-1][k-v[i]]+w[i]){
            cout<<i<<' ';
            k-=v[i];
        }
    cout<<endl;
    cout<<f[n][m]<<endl;

    return 0;
}

题目变式恰好选择k个物品
时间复杂度$(n*m*q) 空间复杂度(m*q)$


    // 状态定义就是从前i个里面选j个物品 容量为 k的最大值
    vector dp(q+5,vector<int>(m+5,-2e9)); 
    dp[0][0]=0; // 必须是恰好的所以不合法的状态不行
    for(int i=1;i<=n;i++){
        for(int j=q;j>=1;j--){
            for(int k=m;k>=v[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-1][k-v[i]]+w[i]);
            }
        }
    }
    cout << dp[n][m] << endl;

在使得至少满足某些要求的时候把非法状态标记,同时注意是至少所以可以多
两个要求的至少满足

时间复杂度$(n*m*k) 空间复杂度(n*m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 25, M = 85;

int dp[N][M];

int n,m,k;

int main(){

    cin >> n >> m;

    cin >> k;

    memset(dp,0x3f,sizeof dp);

    dp[0][0] = 0;

    while(k--){
        int a,b,c; cin >> a >> b >> c;

        for(int i=n;i>=0;i--)
            for(int j=m;j>=0;j--)
                dp[i][j] = min(dp[i][j],dp[max(i-a,0)][max(j-b,0)]+c);
    }

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

    return 0;
}

2.完全背包

时间复杂度$(n*m) 空间复杂度(m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N],dp[N];

int n,m;

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=v[i];j<=m;j++)
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);

    cout << dp[m] << endl;

    return 0;
}

路径输出
时间复杂度$(n*m*k) 空间复杂度(n*m)$
k为其中的$max(m/w[i])$

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N];
int dp[N][N];
int n,m;

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;
    for(int i=n;i>=1;i--){
        for(int j=1;j*v[i]<=m;j++){
            if(dp[i][m]==dp[i-1][m-j*v[i]]+j*w[i]){
                cout << i << ' ' << j << endl;
                m -= j*v[i];
                break;
            }
        }
    }

    return 0;
}

3.多重背包(每个物品有数量限制)

时间复杂度$(n*m*k) 空间复杂度(n*m)$
k为其中的$max(s[i])$

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int s[N],v[N],w[N],dp[N];

int n,m;

int main(){

    cin >> n >> m;

    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];

    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            for(int k=1;k<=s[i] and k * v[i] <= j;k++)
                    dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);

    cout << dp[m] << endl;

    return 0;
}

二进制优化多重背包
时间复杂度$(n*m*log(k)) 空间复杂度(n*m)$
k为其中的$max(s[i])$

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

const int N = 2010;
int cnt;
int v[N*10],w[N*10],dp[N];

int n,m;

int main(){

    cin >> n >> m;

    for(int i=1;i<=n;i++){
        int a,b,c; cin >> a >> b >> c;
        for(int j=1;j<=c;j*=2){
            ++cnt;
            v[cnt] = j * a;
            w[cnt] = j * b;
            c -= j;
        }
        if(c){
            ++cnt;
            v[cnt] = c * a;
            w[cnt] = c * b;
        }
    }

    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);

    cout << dp[m] << endl;

    return 0;
}

单调队列优化背包
时间复杂度$(n*m) 空间复杂度(m)$
对同种余数物品的东西做滑动窗口

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=20010;
int dp[N],g[N],q[N];
int v,w,s;
int n,m;

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        memcpy(g,dp,sizeof dp);
        for(int j=0;j<v;j++){// 表示余数
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v){

                while(hh<=tt and q[hh]<k-s*v) hh++;// 表示我对头元素的位置以及超过了s个v的距离了那我是肯定不会在使用他了、
                // 表示队尾的偏移之后的最大值没有我的大
                while(hh<=tt and g[q[tt]]+(k-q[tt])/v*w <= g[k]) tt--;
                q[++tt]=k;
                dp[k]=max(dp[k],g[q[hh]]+(k-q[hh])/v*w);
            }
        }
    }
    cout<<dp[m]<<endl;

    return 0;
}

4.分组背包(每组只能选一个)

时间复杂度$(n*m*k) 空间复杂度(n*m)$
k为其中的$max(s[i])$

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int s[N],v[N][N],w[N][N],dp[N];

int n,m;

int main(){

    cin >> n >> m;

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

    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s[i];k++)
                if(v[i][k] <= j)
                    dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k]);

    cout << dp[m] << endl;

    return 0;
}

5.有依赖性质的背包

树上的背包,选了我就必须选择我的父节点

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int v[N],w[N];
int dp[N][N];

int n,m,rt;

vector<int> g[N];

void dfs(int u,int fa){

    for(int i=v[u];i<=m;i++) dp[u][i] = w[u];

    for(auto&x:g[u]){
        if(x == fa) continue;
        dfs(x,u);

        for(int i=m;i>=v[u];i--)
            for(int j=0;j<=i-v[u];j++)
                dp[u][i] = max(dp[u][i],dp[u][i-j]+dp[x][j]);
    }
}

int main(){

    cin >> n >> m;

    for(int i=1;i<=n;i++){
        int p;
        cin >> v[i] >> w[i] >> p;
        if(~p){
            g[i].push_back(p);
            g[p].push_back(i);
        }
        else rt = i;
    }

    dfs(rt,-1);

    cout << dp[rt][m] << endl;

    return 0;
}

给你一堆关系使得(a,b)选择a的物品必须严格大于b的物品,那么可以抽象为图论,然后把子权中加起来实现严格大于
时间复杂度$(n*m+n*n) 空间复杂度(m)$

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m,T;
int dp[N],p[N];
LL w[N];
bool in[N];
vector<int> g[N];
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void dfs(int u){
    for(auto&v:g[u]){
        w[v] += w[u];
        dfs(v);
    }
    if(!g[u].empty()) T -= w[u];// 表示严格的大于关系
}
void solve(){

    cin>>n>>m>>T;
    for(int i=1;i<=n;i++) cin>>w[i],p[i]=i;
    bool ok = false;
    while(m--){
        int a,b; cin>>a>>b;
        in[b]=true;
        g[a].push_back(b);
        int fa = find(a), fb = find(b);
        if(fa==fb){
            ok = true;
        }
        else{
            p[fa]=fb;
        }
    }
    if(ok){// 表示矛盾了
        cout << 0 << endl;
        return ;
    }
    for(int i=1;i<=n;i++) if(!in[i]) dfs(i);

    dp[0] = 1;
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=T;j++){
             dp[j] += dp[j-w[i]];
             dp[j] %= mod;
        }
    cout << dp[T] << endl;

    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
         solve();
    }
}

6.背包求方案数

背的价值最多的时候的方案数量
时间复杂度$(n*m) 空间复杂度(m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,mod = 1e9+7;

int f[N],g[N];

int n,m;

int main(){

    // 表示体积恰好为i的时候的fi的最大值是多少
    memset(f,-0x3f,sizeof f);
    f[0] = 0;
    g[0] = 1; // 表示体积为i时最大值的方案数

    cin >> n >> m;

    while(n--){

        int v,w; cin >> v >> w;

        for(int j=m;j>=v;j--){
            int mx = max(f[j],f[j-v]+w);
            int op = 0;
            if(f[j] == mx) op = g[j];
            if(f[j-v]+w == mx) op = (op+g[j-v]) % mod;
            f[j] = mx , g[j] = op;
        }
    }



    int mx = 0;
    for(int j=1;j<=m;j++) mx = max(mx,f[j]);


    int ans = 0;
    for(int j=0;j<=m;j++)
        if(f[j] == mx){
            ans = (ans+g[j]) % mod;
        }

    cout << ans << endl;

    return 0;
}

7.其他背包都是在上面的情况下进行变形

有的是改变维度,把某一维度修改,有的是增加维度来表示题目要求的状态,核心还是状态转移方程,你的定义转移下去

add : 反悔贪心 + 背包
一般而言依照题目意思可以推理出来有一部分需要连续的选择,如在本身的基础上加上k个物品免费

0 评论

App 内打开