背包问题学习及归纳

时间:2021-12-10 15:49:04

1.01背包问题

      顾名思义,及每种物品可以选择放或不放,于是就有了最朴素的转移式:f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]},然后考虑优化空间,可转换为f[j]=max(f[j],f[j-w[i]]+c[i])注意j要逆序的从m到1(保证从已决定推到未决定);

2.完全背包问题

    与01背包类似,但是关键的不同在于其j要顺序的从1到n,因为需要一个可能已选的子结果,然后同理可得f[j]=max(f[j],f[j-w[i]]+c[i]);

3.多重背包问题

   基本想法是f[i][v]=max(f[i][j],f[i-1][j-k*w[i]+k*c[i]),(0<=k<=n[i]&&k*w[i]<=j);转换为01背包问题即把每一个拆分为n[i]个,这样时间和空间的复杂度为O(V*sum(n[i]));然后考虑优化,把每件物品分成若干件2^0,2^1,2^2,2^3,2^(k-1),n[i]-2^k+1(即剩下的),这样既可把时间和空间复杂度降一个log.

背包问题学习及归纳背包问题学习及归纳
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,cnt,m;
int f[10010];
int p[10010],c[10010];
int main(){
    scanf("%d%d",&n,&m);
    int x,y,z,t;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z);
        t=1;
        while(z>=t){//转换 
            p[++cnt]=x*t;
            c[cnt]=y*t;
            z-=t;
            t*=2;
        }
        p[++cnt]=x*z;
        c[cnt]=y*z;
    }
    for(int i=1;i<=cnt;i++)//01背包 
        for(int j=m;j>=p[i];j--)
            f[j]=max(f[j],f[j-p[i]]+c[i]);
    printf("%d",f[m]);
    return 0;
}
View Code

4、二维费用

    其实并没有什么不同,就是在前三个的基础上再加一个状态f[i][v][u]=max(f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]);

    例题:潜水员https://blog.csdn.net/sslgz_yyc/article/details/70337182;

背包问题学习及归纳背包问题学习及归纳
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int v,u,n;
int a[1010],b[1010],c[1010];
int f[1010][1010];
int main(){
    scanf("%d%d%d",&v,&u,&n);
    //求最小值要注意先初始化较大值
    memset(f,127,sizeof(f));
    f[0][0]=0; 
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for(int i=1;i<=n;i++)
        for(int j=v;j>=0;j--)
            for(int k=u;k>=0;k--){
                int x1=min(v,j+a[i]),x2=min(u,k+b[i]);
                f[x1][x2]=min(f[x1][x2],f[j][k]+c[i]);
            }
    printf("%d",f[v][u]);
}
View Code

5、依赖性 

       例题 https://www.luogu.org/problemnew/show/P1064;金明的预算方案,这道题就提到从属关系,但是注意到附件最多有两个,所以在01背包的基础上再加上三次比较即可。

背包问题学习及归纳背包问题学习及归纳
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
//在01背包的基础上弄4次判断;(因为附件最多两件) 
int n,m;
int a[60][3];
int v[100],w[100];
int f[100100];
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[i]=x;
        w[i]=y;
        if(z==0)a[i][0]=i;
        else{
            if(a[z][1]==0)a[z][1]=i;
            else a[z][2]=i;
        }
    }
    for(int i=1;i<=m;i++)
        if(a[i][0])
        for(int j=n;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]);
            if(a[i][1]&&j>=v[i]+v[a[i][1]]) f[j]=max(f[j],f[j-v[i]-v[a[i][1]]]+v[i]*w[i]+v[a[i][1]]*w[a[i][1]]);
            if(a[i][2]&&j>=v[i]+v[a[i][2]]) f[j]=max(f[j],f[j-v[i]-v[a[i][2]]]+v[i]*w[i]+v[a[i][2]]*w[a[i][2]]);
            if(a[i][1]&&a[i][2]&&j>=v[i]+v[a[i][1]]+v[a[i][2]]) f[j]=max(f[j],f[j-v[i]-v[a[i][1]]-v[a[i][2]]]+v[i]*w[i]+v[a[i][1]]*w[a[i][1]]+v[a[i][2]]*w[a[i][2]]);          
        }
    printf("%d",f[n]);
    return 0;
}
View Code

    然后我们考虑将其推广为附件没有被限制个数的问题。第一反应是如原来那样枚举,但是显然时间会超,因为每次只能选择一中策略,所以一个主件和附件几何即为一个物品组,每个策略对应一件物品,所以我们先对主件i的附件合集进行一个01背包,就可将其转换为V-w[i]+1个物品,对于一个费用为w[i]+k的价值为f[k]+c[i];然后就...; 

背包问题学习及归纳背包问题学习及归纳
#include<cstring>
#include<cstdio>
#include<algorithm>
#include <iostream>
using namespace std;
const int maxn=1000+10;
int w[maxn],b[maxn];
int f[maxn];
int max(int a,int b)
{
    return a>b? a:b;
}
int main()
{
    int n,v;
    int i,j,k;
    int t1,t2;
    while(scanf("%d%d",&n,&v)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
         scanf("%d%d",&w[i],&b[i]);
        }
        memset(f,0,sizeof(f));
        for(i=1;i<=n;i++)
        if(b[i]==i)//找出主件
        {
            memset(c,0,sizeof(c));
                 for(t2=1;t2<=n;t2++)//对附件进行01背包处理,使得在相同体积下得到的价值最大
                if(b[t2]==i&&b[t2]!=t2)
                {for(t1=v-1;t1>=0;t1--)
                 if(t1-1>=0)
                 c[t1]=max(c[t1],c[t1-1]+w[t2]);
                }
                c[v]=c[v-1]+w[i];
                for(j=v;j>=0;j--)
                for(k=1;k<=v;k++)//此时看作相当于"V件物品",每件”物品体积“相当为'k',"价值为",c[k-1]+w[i],(i为主件)
                {if(j-k>=0)
                 f[j]=max(f[j],f[j-k]+w[i]+c[k-1]);
                }
            }
        printf("%d\n",f[v]);
    }
    return 0;
}
View Code

6.方案总数

    其实非常的简单,改成和就可以。

7.比较

       1、首先便是01背包和完全背包的比较,这两类其实区别很明显,一个是只有一个,一个是无限个数,而使用方法就要注意,唯一的差别是01背包是逆序的,完全背包是顺序的(J的循环)时间复杂度都近似于O(nm),而空间复杂度皆为O(m);

       2、多重背包特点是每类有有限个的选取个数,二维费用则是有两个限制条件,注意两者都是建立在01背包的基础上;

       3、依赖性这种题更多的是树形dp的应用,重点在于理解;

8.总结

       1、背包问题是很特殊的一类题,题目的设问往往是问能做到什么的最大值或最小值,各种不同的应用也是分别明显,至于考场可能出现的其他变式也之不过是这01背包的基础上做修改和衍生,重点永远是降低复杂度。