加载中…
个人资料
一叶知秋
一叶知秋
  • 博客等级:
  • 博客积分:0
  • 博客访问:424,864
  • 关注人气:82
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

01背包问题

(2013-03-26 21:19:12)
标签:

背包问题

算法

杂谈

分类: 数据结构与算法

0-1背包问题:

问题描述:

N件物品和一个容量为V的背包。第i件物品的重量是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

     这个问题的特点是:每种物品只有一件,可以选择放或者不放。

算法基本思想:

利用动态规划思想 ,子问题为:

f[i][v]表示前i件物品放入一个容量为v的背包可以获得的最大价值。

其状态转移方程是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}  

//这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。

解释一下:将前i件物品放入容量为v的背包中这个子问题,如果只考虑第i件物品放或者不放,那么就可以转化为只涉及前i-1件物品的问题

即:1、如果不放第i件物品,则问题转化为i-1件物品放入容量为v的背包中

2、如果放第i件物品,则问题转化为i-1件物品放入剩下的容量为v-c[i]的背包中”(此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i])

f[i][v]的值就是12中最大的那个值。

(注意:f[i][v]有意义当且仅当存在一个前i件物品的子集,其重量总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。)

优化空间复杂度:

以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)

上面f[i][v]使用二维数组存储的,可以优化为一维数组f[v],将主循环改为:

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

即将第二层循环改为从V..0逆序

解释一下:

假设最大容量M=10,物品个数N=3,物品大小w{3,4,5},物品价值p{4,5,6}

当进行第i次循环时,f[v]中保存的是上次循环产生的结果,即第i-1次循环的结果(i>=1)。所以f[v]=max{f[v],f[v-c[i]]+w[i]}这个式子中,等号右边的f[v]f[v-c[i]]+w[i]都是前一次循环产生的值。

i=1时,f[0..10]初始值都为0。所以

f[10]=max{f[10],f[10-c[1]]+w[1]}=max{0,f[7]+4}=max{0,0+4}=4;

f[9]=max{f[9],f[9-c[1]]+w[1]}=max{0,f[6]+4}=max{0,0+4}=4;

......

f[3]=max{f[3],f[3-c[1]]+w[1]}=max{0,f[0]+4}=max{0,0+4}=4;

f[2]=max{f[2],f[2-c[1]]+w[1]}=max{0,f[2-3]+4}=0;//数组越界?

f[1]=0;

f[0]=0;

i=2时,此时f[0..10]经过上次循环后,都已经被重新赋值,即f[0..2]=0,f[3..10]=4。利用f[v]=max{f[v],f[v-c[i]]+w[i]}这个公式计算i=2时的f[0..10]的值。

i=3时同理。

如下图所示:


01背包问题

因此,利用逆序循环就可以保证在计算f[v]时,公式f[v]=max{f[v],f[v-c[i]]+w[i]}等号右边的f[v]

f[v-c[i]]+w[i]保存的是f[i-1][v]f[i -1][v-c[i]]的值

因为是逆序,所以在改变f[v]的值时,需要用到的上次循环产生的数据还没有被覆盖,因此,存在优化空间。

i=N时,得到的f[V]即为要求的最优值。

初始化的细节问题:

     在求最优解的背包问题中,一般有两种不同的问法:

1、要求恰好装满背包时的最优解;

2、求小于等于背包容量的最优解,即不一定恰好装满背包。

这两种问法,在初始化的时候是不同的。

1、要求恰好装满背包时的最优解:

在初始化时除了f[0]0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果不能恰好满足背包容量,即不能得到f[V]的最优值,则此时f[V]=-∞,这样就能表示没有找到恰好满足背包容量的最优值。

2、求小于等于背包容量的最优解,即不一定恰好装满背包:

如果并没有要求必须把背包装满,而是只希望价值尽量大,初始化时应该将f[0..V]全部设为0

一个常数优化

前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进。

由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可。以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的

for i=1..N

          for v=V..0

可以改成

for i=1..n

        bound=max{V-sum{w[i..n]},c[i]}

        for v=V..bound

这对于V比较大时是有用的。

总结

01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。


示例代码:

#include
#include
using namespace std;
const int MIN=0x80000000;
const int N=3  //
物品数量
const int V=5 //背包容量
int f[V+1];

int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[])
{
 int W[4]={0,7,5,8};      //
物品权重
 int C[4]={0,2,3,4};      //物品大小
 int result=Package(W,C,N,V);
 if(result>0)
 {
  cout<<endl;
  cout<<"the opt value:"<<result<<endl;
 }
 else
  cout<<"can not find the opt value"<<endl;
 return;
}

int Package(int *W,int *C,int N,int V)
{
 int i,j;
 memset(f,0,sizeof(f));  //
初始化为0

 for(i=1;i<=V;i++)               //
此步骤是解决是否恰好满足背包容量,
  f[i]=MIN;                //恰好满足背包容量,即正好装满背包,则加上此步骤,若不需要恰好,则初始化为0
   
 for(i=1;i<=N;i++)
  for(j=V;j>=C[i];j--)    //
注意此处是逆序,还有要保证j-c[i]>=0;
  {
   f[j]=(f[j]>f[j-C[i]]+W[i])?f[j]:(f[j-C[i]]+W[i]);
   cout<<"f["<<i<<"]["<<j<<"]="<<f[j]<<endl;
  }
 return f[V];
}

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:int64
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇int64
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有