背包DP

· · 个人记录

背包是线性DP中重要而特殊的模型

01背包

题目描述

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，他们的重量分别是W1，W2，…，W能，他们的价值分别是C1，C2，…，Cn，求旅行者能获得最大总价值。

简述：n件物品放或不放

建立状态转移方程

f[i][j]表示从前i个物品中选出了总体积为j的物品放入背包，物品的最大价值和

枚举i:1~n个物品
    枚举j:0~m的背包负重
        if(j>=w[i])
            f[i,j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])
        else 
            f[i][j]=f[i-1][j];

如下完整代码

#include <cstdio>
#include <iostream>
using namespace std;
int m,n;
int weight[35],value[35];
int f[650][650]; 
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&weight[i],&value[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(j>=weight[i]){
                f[i][j]=max(f[i-1][j-weight[i]]+value[i],f[i-1][j]);
            }else {
                f[i][j]=f[i-1][j];
            }
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

我们可以发现，每一阶段i的状态只与上一阶段i-1的状态有关。 因此，我们可以取消第一维表示i的状态，降低空间开销，这称为“滚动数组”

但需注意

在第二重循环处，我们使用了倒序循环

模拟一下

循环到j时:

1.f数组的后半部分 f [ j ~ m ] 处于第i个阶段，也就是已经考虑过放入第i个物品的情况

2.前半部分 f [ 0 ~ j-1 ]处于第i-1个阶段，也就是还没有更新第i个物品 接下来j不断减小，意味着我们总是用第i-1个阶段的状态向第i个阶段的状态转移

符合线性DP原则，进而保证了第i个物品只会被放入背包一次

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 650
using namespace std;
int f[maxn];
int n,v;
int c[40],w[40];

int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&w[i],&c[i]); 
    for(int i=1;i<=n;i++)
        for(int j=v;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d",f[v]); 
    return 0;
}

运用

题目大意：先读入正整数N（1< N< 100）和M(1< M< 10000)， 再读入N个正数（可以有相同的数字，每个数字均在1000以内）， 在这N个数中找出若干个数， 使它们的和是M， 把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。

#include <cstdio>
#include <iostream>
using namespace std;
int n,m,a[105],f[10005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    f[0]=1;//初始化
    for(int i=1;i<=n;++i)
        for(int j=m;j>=a[i];--j)
            f[j]+=f[j-a[i]];
    printf("%d",f[m]);
    return 0;
}

例题金明的预算方案

分主件与附件存储，因为最多两件附件，所以比01两种情况多了三种，取或只取主件或取主件+第一件附件或取主件+第二件附件或主件+两件附件

#include <bits/stdc++.h>
using namespace std;
const int maxn=65;
int n,m,sum,f[32005],c[maxn][maxn];
int p,q;
int w[maxn],v[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&v[i],&p,&q);
        c[q][++c[q][0]]=i;
        w[i]=p*v[i];
    }
    for(int i=1;i<=c[0][0];++i){
        for(int k=n;k>=v[i];--k){
            int a1=(k-v[c[0][i]])>=0?f[k-v[c[0][i]]]+w[c[0][i]]:0;
            int a2=(k-v[c[0][i]]-v[c[c[0][i]][1]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]]+w[c[0][i]]+w[c[c[0][i]][1]]:0;
            int a3=(k-v[c[0][i]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][2]]:0;
            int a4=(k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][2]]-v[c[c[0][i]][1]]]+w[c[0][i]]+w[c[c[0][i]][2]]+w[c[c[0][i]][1]]:0;
            f[k]=max(f[k],max(max(a1,a2),max(a3,a4)));
        }
    }
    printf("%d",f[n]);
    return 0;
}

完全背包

题目描述

有N（<=20）种物品和一个容量为V（<=150）的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

注意：在第二重循环里，我们采用正序循环

这对应着每种物品可以使用无限次
也对应着f[i,j]=f[i,j-w[i]+c[i]]这两个均处于i阶段的状态之间进行转移的方程

上菜

#include <bits/stdc++.h>
using namespace std;
#define maxn 250
int n,v,w[maxn],c[maxn],f[maxn];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=v;++j)
            if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d",f[v]);
    return 0;
}

多重背包

题目描述

第一行 V和N；

以下N行，每行为每种物品的费用，价值和数量。

简述：01+完全背包

#include <bits/stdc++.h>
using namespace std;
#define maxn 250
int n,v,w[maxn],c[maxn],t[maxn],f[maxn];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;++i)scanf("%d %d %d",&w[i],&c[i],&t[i]);
    for(int i=1;i<=n;++i)
        for(int s=1;s<=t[i];++s)
            for(int j=v;j>=1;--j)
                if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d",f[v]);
    return 0;
}

分组背包

题目描述

一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

#include <bits/stdc++.h>
using namespace std;
int v,n,t,f[250];
vector<int>w[20];
vector<int>c[20];

int main(){
    scanf("%d%d%d",&v,&n,&t);
    int wi,ci,p;
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&wi,&ci,&p);
        w[p].push_back(wi);
        c[p].push_back(ci);
    }
    for(int i=1;i<=t;++i)
        for(int j=v;j>=0;--j)
            for(int k=0;k<(int)w[i].size();++k)
                if(j>=w[i][k])
                    f[j]=max(f[j],f[j-w[i][k]]+c[i][k]);
    printf("%d",f[v]);
    return 0;
}

[POI2005]Bank notes

需二进制优化的分组背包

暂时先不求方案的两种写法，单纯看二进制优化

写法一

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=20005;
int n,m,a[202],g[202],f[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i) scanf("%d",&g[i]);
    scanf("%d",&m);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;++i){
        for(int k=1;g[i];k<<=1){//二进制优化 
            k=min(k,g[i]);
            g[i]-=k;
            for(int j=m;j>=a[i]*k;--j) f[j]=min(f[j],f[j-a[i]*k]+k);//倒序枚举 
        }
    }
    printf("%d",f[m]);
    return 0;
}

写法二

#include <bits/stdc++.h>
using namespace std;
const int maxn=20005;
int n,m,x,a[202],ans[202],dp[maxn];
int tot,v[maxn],w[maxn],k[maxn];
inline void add(int v1,int w1,int k1){v[++tot]=v1;w[tot]=w1;k[tot]=k1;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        for(int j=1;j<=x;x-=j,j<<=1) add(j,j*a[i],i);//千万注意先减再移位
        if(x) add(x,x*a[i],i);
    } 
    scanf("%d",&m);
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=tot;++i){
        for(int j=m;j>=w[i];--j){
            if(dp[j]>dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i];
        }
    }
    printf("%d\n",dp[m]);
    return 0;
}

关于方案怎么破

不得不说一句bool卡内存好手，tot也节省了一大把空间

#include <bits/stdc++.h>
using namespace std;
const int maxn=20005;
int n,m,x,a[202],ans[202],dp[maxn];bool from[3202][maxn];
int tot,v[3201],w[3201],k[3201];
inline void add(int v1,int w1,int k1){v[++tot]=v1;w[tot]=w1;k[tot]=k1;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        for(int j=1;j<=x;x-=j,j<<=1) add(j,j*a[i],i);
        if(x) add(x,x*a[i],i);
    } 
    scanf("%d",&m);
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=tot;++i){
        for(int j=m;j>=w[i];--j){
            if(dp[j]>dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i],from[i][j]=1;
        }
    }
    printf("%d\n",dp[m]);
    int sum=m,cnt=dp[m];
    for(int i=tot;cnt;){
        while(!from[i][sum])i--;
        sum-=w[i];ans[k[i]]+=v[i];cnt-=v[i--];
    }
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}

分组背包是许多树形DP问题状态转移的基本模型

指路：树形DP

混合背包

题目描述

01+完全+分组

#include <cstdio>
#include <iostream>
using namespace std;
int m,n,f[205];
struct node{
    int w,c,p;
}a[31];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].w,&a[i].c,&a[i].p);
    for(int i=1;i<=n;i++){
        if(a[i].p==0){
            for(int t=1;t<=m;t++){
                if(t>=a[i].w) f[t]=max(f[t-a[i].w]+a[i].c,f[t]);
            }
        }else{
            for(int j=1;j<=a[i].p;j++){
                for(int t=m;t>=1;t--){
                    if(t>=a[i].w)
                        f[t]=max(f[t-a[i].w]+a[i].c,f[t]);
                }
            }
        }
    }
    printf("%d",f[m]);
    return 0;
}