首页
登录 | 注册

经典背包问题----(01背包、完全背包、多重背包)

最近在学DP,上周六ACM集训队花一整天的时间共同探讨了最经典的DP--背包问题,对这类问题研究也挺深入的,感谢各队友及老师的讲解,觉得受益匪浅!

(1)01背包

01背包算是最基础的背包问题了,意思就是共有N个物品,一个背包。各物品的重量为Wi,价值为Vi,背包能承受的最大重量为W,求背包能装进去物品的最大价值!分析:其一是变量元素,可知与该结果有关系的就是重量和价值,其次是状态转移。那么显然子问题就是当前的背包重量能装的最大价值,用数组F[i][j]表示的话,背包的剩余重量为j,i为当前物品,F[i][j]保存的就是背包在j容量下装的最大价值,即把1,2,3...i-1个物品装到容量为j的背包中的最大价值。对于第i个物品,有两种选择,放或者不放,当j<wi时,肯定是不能放的,那么F[i][j]=F[i-1][j],若j>=Wi,放第i件物品时,剩余背包容量为j-Wi,此时价值为F[i][j]=F[i-1][j-Wi]+Vi,做价值最大的选择,则:F[i][j]=MAX(F[i-1][j],F[i-Wi]+Vi。可由底层到顶层推,那么F[1][W]为最终值,代码如下:

int DP1()
{
    for(int j=W;j<=0;j++)
    {
        if(j<w[N])
          f[N][j]=0;
        else
          f[N][j]=v[i];
    }
    for(int i=N-1;i>=1;i--)
        for(int j=0;j<=W;j++)
       {
        if(j<w[i])
            f[i][j]=f[i+1][j];
        else
            f[i][j]=max(f[i+1][j],f[i+1][j-w[i]]+v[i]);
       }
    return f[1][W];
}

优化:由于F[i][j]是从前一个状态F[i-1][j]得到的,只与前一个状态有关,那么即可优化为一维滚动数组F[],需注意F必须是从右往左计算,因为F[j]保存的是f[i-1][j]的值,F[j-Wi]保存的是f[i-1][j-Wi]的值,而不是f[i][j-Wi],这样,F[j]保存的就是max(f[i-1][j],f[i-1][j-Wi])覆盖原来的f[i-1][j]//注意:便于叙述,这里F[]表示优化的滚动数组,f[][]是原来的二维数组。代码如下:

int DP1()
{
  memset(f,0,sizeof(f));
  for(int i=1;i<=N;i++)
    for(int j=W;j>=w[i];j--)
      f[j]=max(f[j],f[j-w[i]+v[i])
    return f[W];
}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

(2)完全背包

完全背包是在01背包的基础上,物品为的数量由一个变为无限个,求满足重量的条件下最大价值。由上述的01背包,很容易就能想到通过枚举每种物品的数量来求最大值,那么需要再加一层循环来限定第i件物品的数量,此时公式为:F[i][j]=MAX(F[i-1][j],F[i-1][j-k*w[i]]+k*v[i])1<=k<=W/Wi不过很遗憾,这种算法的复杂度非常高,再仔细考虑一下,会发现若两件物品i、j满足v[i]>=v[j]且w[i]<=w[j],则将物品j去掉,不用考虑。即,如果一个物品A是占的地少且价值高,而物品B是占地多,但是价值不怎么高,那么肯定是优先考虑A物品的。那么公式即为:F[i][j]=MAX(F[i-1][j],F[i][j-w[i]]+v[i],代码如下:


for(int i=1;i<=N;i++)
    for(int j=0;j<=W;j++)
    {
      if(j<w[i])
        f[i][j]=f[i-1][j];
      else
        f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i];
    }

-------------------------------------------------------------------------------------------------------

(3)多重背包

多重背包是每件物品都有给定的数量,如果按照安全背包的思想,每件物品的数量为num[i],即1<=k<=num[i],若按三层循环来写,复杂度也挺高!那么有一个非常奇妙的二进制思想,任何数都可以用二进制来表示,如果一个数N能用1,2,4,8,16....的和来表示的话,那么从1到N之间的任意数字都可以用这些数来表示,比如第i种物品的数量为7,重量为2,价值为3,分析:7可分为1,2,4即该种物品被分成重量为2*1,2*2,2*4价值为3*1,3*2,3*4的三种物品,那么就大大减少了物品的数量,推测以一亿个物品按这种方式最多分为30多个物品,这样就能用01背包的知识来解决这个问题,代码如下:

struct ss

{

   int x;//物品重量

   int y;//物品价值

   int z;//物品数量

}s[1000];//假设1000种物品

int DP1()
{
   int t=-1;
   for(int i=1;i<=N;i++)
   {
    t++;
    int sum=1;
    int sum1=1;

    w[t]=s[i].x;

    v[t]=s[i].y;
    while(sum1<s[i].z)
    {
       sum*=2;
       sum1+=sum;
       if(sum1<s[i].z)
       {
        w[t]=sum*s[i].x;
        v[t]=sum*s[i].y;
       }
    }
       if(sum1!=s[i].z)
       {
           t++;
           w[t]=(s[i].z-(sum1-sum))*s[i].x;
           v[t]=(s[i].z-(sum1-sum))*s[i].y;
       }
   }
    memset(f,0,sizeof(f));
    for(int i=0;i<=t;i++)
       for(int j=W;j>=w[i],j--)
          f[j]=max(f[j],f[j-w[i]+v[i]);
    return f[W];
}




2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.010 s.
京ICP备10005923号