欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

背包问题

程序员文章站 2022-06-07 14:20:18
01背包 n个物品,v的体积,求最多能装下的价值 每个物品只能拿一次 https://www.acwing.com/problem/content/2/ 1 #include 2 using namespace std; 3 int main(){ 4 int N,V, ......

 

01背包

n个物品,v的体积,求最多能装下的价值

每个物品只能拿一次

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n,v,dp[1005] = {0};
 5     scanf("%d%d",&n,&v);
 6     for(int i=1,x,y;i<=n;i++){
 7         scanf("%d%d",&x,&y);
 8         for(int j=v;j>=x;j--){
 9             dp[j] = max(dp[j],dp[j-x]+y);
10         }
11     }
12     printf("%d\n",dp[v]);
13     return 0;
14 }

完全背包

n个物品,v的体积,求最多能装下的价值

每个物品可以拿无限次

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n,v,dp[1005] = {0};
 5     scanf("%d%d",&n,&v);
 6     for(int i=1,x,y;i<=n;i++){
 7         scanf("%d%d",&x,&y);
 8         for(int j=x;j<=v;j++){
 9             dp[j] = max(dp[j],dp[j-x]+y);
10         }
11     }
12     printf("%d\n",dp[v]);
13     return 0;
14 }

 

多重背包

n个物品,v的体积,求最多能装下的价值

每个物品可以拿ki

一个优化:(二进制优化)

显然我们没有必要跑全ki次,判断下能用完全背包的就用完全背包好了

不能用完全背包的,考虑一个等价的次数,即,每次取1个,2个,4个。。。ki-2j+1个

j是最大的能使ki-2j+1>0的数

也就是说我们将ki二进制拆分了

时间复杂度为o(n*m*log(∑ki))

另一个优化:(单调队列优化)

————咕咕咕——————

时间复杂度o(n*m)

/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
int main(){
    ll n,v,dp[20005] = {0};
    scanf("%lld%lld",&n,&v);
    for(ll i=1,x,y,z;i<=n;i++){
        scanf("%lld%d%lld",&x,&y,&z);
        if(x*z>v){
            for(int j=x;j<=v;j++){
                dp[j] = max(dp[j],dp[j-x]+y);
            }
        }else{
            for(ll tmp = 1;z-tmp+1 > 0;tmp <<= 1){
                ll k = (z-(tmp<<1)+1)<0?z-tmp+1:tmp;
                for(ll j=v;j>=x*k;j--){
                    dp[j] = max(dp[j],dp[j-x*k]+y*k);
                }
            }
        }
    }
    printf("%lld\n",dp[v]);
    return 0;
}

 

混合背包

前三个混在一起,加个if判断即可

/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 2e4+7;
int dp[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--){
        int k,value,cnt;
        scanf("%d%d%d",&k,&value,&cnt);
        if(cnt == -1){
            for(int i=m;i>=k;i--){
                dp[i] = max(dp[i],dp[i-k]+value);
            }
        }else if(cnt == 0 || k*cnt>=m){
            for(int i=k;i<=m;i++){
                dp[i] = max(dp[i],dp[i-k]+value);
            }
        }else{
            for(int i=1;cnt-i+1>0;i<<=1){
                int tmp = (cnt-(i<<1)+1)<0?cnt-i+1:i;
                for(int j=m;j>=tmp*k;j--){
                    dp[j] = max(dp[j],dp[j-tmp*k]+tmp*value);
                }
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

 

二维费用的背包问题

物体不止有体积这个限制条件,还有质量这个限制条件

n个物体,v的背包容积,m的负重限制,还是01背包只能拿一个

/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 1e3+7;
int dp[maxn][maxn];
int main(){
    int n,v,m;
    scanf("%d%d%d",&n,&v,&m);
    while(n--){
        int volum,weight,value;
        scanf("%d%d%d",&volum,&weight,&value);
        for(int i=v;i>=volum;i--){
            for(int j=m;j>=weight;j--){
                dp[i][j] = max(dp[i][j],dp[i-volum][j-weight]+value);
            }
        }
    }
    printf("%d\n",dp[v][m]);
    return 0;
}

 

分组背包问题

每组只能拿一个,这样调整下for的顺序就好了

/*author:revolia*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 1e3+7;
int dp[maxn];
int weight[maxn],value[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--){
        int cnt;
        scanf("%d",&cnt);
        for(int i=1;i<=cnt;i++){
            scanf("%d%d",&weight[i],&value[i]);
        }
        for(int i=m;i>=0;i--){
            for(int j=1;j<=cnt;j++)if(i>=weight[j]){
                dp[i] = max(dp[i],dp[i-weight[j]]+value[j]);
            }
        }
    }
    printf("%d\n",dp[m]);
    return 0;
}

 

有依赖的背包问题

要想拿当前物体,必须拿它的父亲

用dfs先处理处子节点,然后拿出当前节点(因为必须拿当前才能拿子节点)

做一个背包,然后把当前节点更新进去

/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 107;
int n,m,root;
int head[maxn],to[maxn],next[maxn],tot = 1;
int dp[maxn][maxn],val[maxn],wei[maxn];
void add(int u,int v){
    to[tot] = v;
    next[tot] = head[u];
    head[u] = tot++;
}
void dfs(int u){
    for(int i=head[u];i;i=next[i]){
        int son = to[i];
        dfs(son);
        for(int j=m-wei[u];j>=wei[son];j--){
            for(int k=wei[son];k<=j;k++){
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[son][k]);
            }
        }
    }
    for(int i=m;i>=wei[u];i--)dp[u][i] = dp[u][i-wei[u]]+val[u];
    for(int i=0;i<wei[u];i++)dp[u][i] = 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%d%d%d",&wei[i],&val[i],&x);
        if(~x)add(x,i);
        else root = i;
    }
    dfs(root);
    printf("%d\n",dp[root][m]);
    return 0;
}

 

背包问题求方案数

加一个数组,更新即可

/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod = 1e9+7;
int n,m;
int dp[maxn],ans[maxn];
int main(){
    scanf("%d%d",&n,&m);
    fill(ans,ans+n,1);
    for(int i=1,x,y;i<=n;i++){
        scanf("%d%d",&x,&y);
        for(int j=m;j>=x;j--){
            if(dp[j]<dp[j-x]+y){
                ans[j] = ans[j-x];
            }else if(dp[j] == dp[j-x]+y){
                ans[j] += ans[j-x];
                ans[j] %= mod;
            }
            dp[j] = max(dp[j],dp[j-x]+y);
        }
    }
    printf("%d\n",ans[m]);
    return 0;
}

 

背包问题求具体方案

求字典序最小的方案

倒着来一遍背包,然后正着扫描一遍

/*author:revolia*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 1e3+7,mod = 1e9+7;
int n,m;
int dp[maxn][maxn];
int x[maxn],y[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<x[i];j++)
            dp[i][j] = dp[i+1][j];
        for(int j=x[i];j<=m;j++)
            dp[i][j] = max(dp[i+1][j],(dp[i+1][j-x[i]]+y[i]));
    }
    for(int i=1;i<=n;i++){
        if(m>=x[i] && dp[i][m] == dp[i+1][m-x[i]]+y[i]){
            printf("%d ",i);
            m -= x[i];
        }
    }
    return 0;
}