【模板】各种背包问题&讲解

2018/03/06 19:22
阅读数 12

                                       背包问题集合

  一般来说,动态规划(DP)都是初学者最难闯过的一关,而在这里详细解说动态规划的一种经典题型:背包问题

这里介绍的背包分为以下几种:01背包,完全背包,多重背包,混合背包,二维费用的背包。(以后会持续更新)

【一:01背包】

首先放上例题:

 

01背包问题

【题目描述】:

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

【输入格式】:

第一行:两个整数,M,(背包容量,M<=200)和N(物品数量N<=30)

第2至N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值。

【输出格式】:仅一行,一个数,表示最大总价值。

【输入样例#1】:

10 4

2 1

3 3

4 5

7 9

【输出样例#1】:12

【输入样例#2】:

8 4

5 6

4 2

1 2

 

01背包问题可以说是最简单的背包问题,简单之处就在:他的每一个物品都只有一个

首先定义一个f[MAXN][MAXN]数组,用来记录最大价值。即:f[i][v]表示的就是当前i件物品放入一个容量为v的背包的时候可以获得的最大价值。

01背包的状态转移方程式便是:f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])

众所周知DP问题最重要的便是状态转移方程式了,那么这个状态转移方程式究竟是怎么来的呢??

 

详解来啦“!!!

既然说了是“将第i件物品放入背包”,那么如果只考虑第i件物品的方式策略,那么就只和第i-1件物品有关了,如果是放第i件物品,那么问题就转化为:“前i-1件物品放入容量为v的背包中”,此时能够获得的最大价值就是f[i-1][v-w[i]],也就是第i-1件物品放入容量为v(原来的总容量)减去w[i](第i件物品的占容)产生的最优价值,再加上放通过入第i件物品增加的价值c[i]。

那么放入第i件物品产生的最大价值就是要在”放“,或者是”不放“中选择了,”不放“的话,产生的价值就是f[i-1][v]”放“的话,产生的最大价值就是,f[i-1][v-w[i]]+c[i])那么我们应该怎么选择呢,很简单,取最大的,就是产生的最大价值啦。

若物品数量为n,背包总容量为m,那么循环到最后,答案也就是f[n][m]啦。

那么附上代码:::

#include<bits/stdc++.h>
#define MAXN 0x7ff
using namespace std;
int m,n,w[MAXN],c[MAXN];
int f[MAXN][MAXN],i,j;//f[i][v]表示第i件物品放入容量为v的背包所能产生的最大价值。 
int maxn(int x,int y)//比较,输出最大值 
{
    if(x>y)
    return x;
    else 
    return y;
}
int main()
{
    cin>>m>>n;    
    for(i=1;i<=n;i++)
        cin>>w[i]>>c[i];//输入不解释 
    for(i=1;i<=n;i++)
        for(j=m;j>0;j--)
        {
            if(w[i]<=j)
            f[i][j]=maxn(f[i-1][j],f[i-1][j-w[i]]+c[i]);//状态转移方程式。 
            else f[i][j]=f[i-1][j];
        }
        cout<<f[n][m];
        return 0;
}

好了以上就是最简单的01背包模板了qwq。

【二:完全背包问题】

还是例题打头阵。

完全背包问题

【题目描述】

设有n种物品,每种物品有一个价值,但每种物品的数量是无限的,同时有一个背包,最大承载量微m,今从n种物品中选取若干件,(同一种物品可以多次选举)使其重量的和小于等于m,而且价值的和最大。

【输入】共N+1行

第一行:两个整数:M(背包容量M<=200)和N(物品数量,N<=30);

第二行至第N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值。

【输出】

近一行:一个数,表示最大的价值;

【输入样例】

10 4

2 1

3 3

4 5

7 9

【输出样例】

12

 

有的小伙伴们可能一看到例题就会发现一个与01背包不同的地方:每种物品的数量是无限多的。没错,这就是完全背包问题。其实这个问题没有比01背包难多少,只是不是很好想。

既然每种物品所取的数量可能是1,2,3.......,所以与它相关的策略便不是取或者不取的问题了,而是,取不取,取多少的问题了。既然同样是背包问题,那么我们可不可以考虑延续01背包的方法来做呢,答案是Yes。其实与01背包不同的地方就是只有放进去的每种物品的件数不一定是1就是了,那么只要多一重关于每种物品取多少的循环不就可以了吗。相对的,其状态转移方程式也要略有改动,变为:f[i][v]=max(f[i-1][v-k*w[i]]+k*c[i],f[i-1][v]),可见就是比01背包多了一个k而已,而这个k就是循环的这第i种物品取的件数。

现在解释一下原因:首先我们想一下为甚么在上题中的01背包代码中第二重循环是for(int j=m;j>=0;j--)而不是for(int j=1;j<+m;j++)呢??(你就没有怀疑过吗??~~~)

Because~因为:要保证第i次循环里的状态f[i][v]是由状态f[i][[v-w[i]]递推而来的,也就是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝不可能选入第i种物品的子结果f[i][v-w[i]]。如果如果还不是很明白,大家可以画一个表格来自己推一下,看看逆序和正序时得到的结果有什么不同。。。。。

好了重点来了!! : 现在大家已经知道了01背包的顺序,那么现在问题来了:完全背包的顺序呢??

考虑“加选一件第i种物品”这种策略时,却正需要一个可能已经选入第i种物品的子结果f[i][v=w[i]],所以就可以并且必须采用v=0,.....v的顺序循环,这就是则个简单的程序何以成立的原因啦。

 

然后给大家附上代码::    //不准抄袭!!     好吧像我这种蒟蒻代码有谁会抄呢 呵呵~~

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=31,MAXM=201;
int m,n,w[MAXN],c[MAXN],f[MAXN][MAXM];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
     scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++)
     for(int v=1;v<=m;v++)
      if(v<w[i]) f[i][v]=f[i-1][v];
      else {if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v];
           else f[i][v]=f[i][v-w[i]]+c[i];}
    printf("%d",f[n][m]); return 0;
}//这个码风不是很好看,大家看不惯可以改一改......

 【三:多重背包问题】

好了依然是看例题::

模板例题:庆功会

【题目描述】

设有n种物品,每种物品有一个价值,但每种物品的数量是有限的,同时有一个背包,最大承载量微m,今从n种物品中选取若干件,(同一种物品可以多次选举)使其重量的和小于等于m,而且价值的和最大。

【输入】共N+1行

第一行:两个整数:N(物品数量,N<=30)和M(背包容量M<=200)

第二行至第N+1行,每行两个整数,Wi,Ci,Si,分别表示每个物品的重量、价值、数量。

【输出】

近一行:一个数,表示最大的价值;

【输入样例】

5 1000

80 20 4

40 50 9

30 50 7

40 30 6

20 20 1

【输出样例】

1040

 

  这个题目就又不一样了,因为题目中说的每一件物品的件数是“有限的”,也就是说可以是1、2......但也不是无限。

这个看起来可能就比较e xin,但是如果仔细想一想,其实也并不是很难。

(蒟蒻认为的)重点详解:
做法1:和完全背包接轨:完全背包里面有一个k,用来表示物品的个数,这里面也是一样的,因为对于第i种物品,我们可以设置他有n[i]+1种取数策略,:取0、1.....n[i]件,so我们再次设置一个f[i][v]表示前i种物品放入一个容量为v的背包所能产生的最大价值,那么:f[i][v]=max(f[i-1)[v-k*w[i]]+k*c[i],f[i-1][v]),那么复杂度就是O(V*Σn[i])。

   显然,上方做法时间复杂度太高。于是就有了第二个方法。

做法2:和01背包接轨。大家可能都觉得完全背包比01背包更要高大上一些,但是很不幸,做法2是要远远优于做法1的。先给大家一个引路思想,第i件物品有n[i]的数量,那么是不是可以把它转化为n个数量只有一个的物品呢??看到这里,你恍然大悟:哦,好巧妙。

而事实上,如果你只想到这里,就开始兴奋无脑地开始打代码的话,你就会呵呵进化成神犇了。。。。。您可以算一算如果这样做的话时间复杂度是多少:O(V*Σn[i])  ............

好极了,可是我并没有在逗你啊。。。。。

那么接下来就是优化了,在这里,我们考虑二进制优化

方法:将第i件物品分成若干件物品,每个物品有一个系数l,这件物品的费用和价值军事原来的费用和价值乘以l,使这些系数分别为1,2,4...2(k-1)余出来的再拿出来就是n[i]-2(k+1),且k是满足n[i]-2(k+1)>0的最大整数。(例:13分为1,2,4,6)。

这样就将第i件物品分成了O(logn[i)种物品,将时间复杂度降低成为了O(V*Σlogn[i])的01背包问题,改进是不是很大呢?

下面是代码:

#include<iostream>
#include<cstdio>
#define MAXN 10001
#define MAXM 6001
using namespace std;
int v[MAXN],w[MAXN],f[MAXM];
int n,m,n1;
int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x,y,s,t=1;
        scanf("%d%d%d",&x,&y,&s);
        while(s>=t)
        {
            v[++n1]=x*t;
            w[n1]=y*t;
            s-=t;
            t*=2;
        }
        v[++n1]=x*s;
        w[n1]=y*s;
    }
    for(int i=1;i<=n1;i++)
     for(int j=m;j>=v[i];j--)
      f[j]=max(f[j],f[j-v[i]]+w[i]);
    printf("%d\n",f[m]); return 0;
     
}

【四:混合三种背包问题】

  大概很多人一看到这个就泪奔了,对,没错,就是把01、完全、多重背包混合起来考你。你可能肯定觉得很恶心,觉得难极了,确实,对于没有学过前几种背包的人来说,这是一个很大的挑战,但是不要忘了,我们已经学完了呀!所以,我哦们就可以很轻易地将这一个难题转化为极个简单的子题了!!

  其实也不用怎么解释了,先判断该物品是不是属于完全背包,if(YES)->用完全背包去做,if(NOT)->用混合背包去做(因为01背包本身即是多重背包的一个样例,用多重背包做完全没有问题的。)

  好了下面附上代码:

 

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

【五:二维费用的背包】

  这又是一种新的背包问题了,显而易见,他的费用是二维的。什么叫二维的呢?先来看一道例题,你就能明白了。

                         例题:潜水员

【问题描述】

潜水员为了潜水要使用特殊的装备,他有一个带2种气体的气缸,一个为氧气,一个为氮气,让钱会员下潜的深度需要各种数量的氧和氮,潜水员有一定数量的气缸,每个气缸都有重量和气体容量,潜水员为了完成她的工作需要特定的数量的氧和氮,他完成工作需要气缸的总重的最低限度是多少??

【输入格式】

第一行:两个整数,m,n,(1<=m<=21,1<=n<=79)。他们表示氧,氮各自需要的量。

第二行:为整数k(1<=k<=1000)表示气缸的个数。

此后的k行每行包括一个ai,bi,ci,(1<=ai<=21,1<=bi<=79,c<=ci<=800)三个整数,分别表示第i个气缸里的氧的容量,氮的容量,以及气缸重量。

【输出格式】

仅一行,包含一个整数,为重量和的最低值。

【输入样例】

5 60

5

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

【输出样例】

249

 

好的,我觉得大多数人可能都已经明白了什么叫二维了,在这个例题中,每一个气缸油两种不同的费用,选择这件物品必须同时付出这两种代价,对于每一种代价有一个背包容量,问怎么样选择物品可以得到最大的价值。

接下来不只针对例题,而是对于大多数二维背包题:

  我们可以定义第i种物品的代价分别为a[i]和b[i],两种背包容量分别为V和U,第i件物品的价值为c[i]。

那么显而易见,我们的算法需要增加一维,那么就将我们的f再增加一维即可,那么就有了状态转移方程式::

f[i][v][u]=max)f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i])当然,当物品只取一次是的时候变量v和u采取逆序循环。

但有的时候,很多良心的题经常是将二维背包以一种有一点隐晦的方式表示出来,例如:最多只能取M件物品,此时就又多了一个“件数”的费用,设f[v][m]表示付出费用v,最多选m件的时候可以得到的最大收入。之后便可以针对01、完全、多重背包采用不同的方式进行运算了。最后,在f[0 -> V][1 -> M]范围内寻找答案。

然后,附上【潜水员】例题的代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 1001
#define MAXM 101
using namespace std;
int v,u,k;
int a[MAXN],b[MAXN],c[MAXN];
int f[MAXM][MAXM];
int main()
{
    memset(f,127,sizeof(f));
    f[0][0]=0;
    scanf("%d%d%d",&v,&u,&k);
    for(int i=1;i<=k;i++)
     scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for(int i=1;i<=k;i++)
     for(int j=v;j>=0;j--)
      for(int l=u;l>=0;l--)
      { 
          int t1=j+a[i],t2=l+b[i];;
          if(t1>v) t1=v;
          if(t2>u) t2=u;
          if(f[t1][t2]>f[j][l]+c[i]) f[t1][t2]=f[j][l]+c[i];
      }
      printf("%d",f[v][u]);
      return 0;
}

 

好了,关于背包问题就先说到这里(持续更新。。。),如果有不明白个或者错误的地方可以给我留言。。。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部