题意描述:
有六种不同价值的珠宝若干,问你能否把这些珠宝分成价值相等的两份。当然,每个珠宝是不能切割的。
非常明显这一题是01背包问题,由于珠宝数量巨大,为了提高程序效率,我们要对同种价值的珠宝进行二进制拆分,这样能够迅速减少珠宝的数量(具体说来珠宝数量会变成O(logN)的数量级,N是原来珠宝的个数),二进制拆分后与原来是等效的,想想二进制数就明白了。
01背包的状态转移方程为:
当v<Ci时f[i,v]=f[i-1,v];(1)
当v>=Ci时f[i,v]=Max(f[i-1,v],f[i-1,v-Ci]+Wi);(2)//当第i件物品能够放下时,我们可以选择放,或不放,取决于总价值的大小。
其中v为当前背包的中容量,Ci表示第i件物品的体积,Wi表示第i件物品的价值,f[i,v]表示容量为v的背包在考虑前i件物品后的最大价值。
上面的状态转移方程实现起来要开一个大小为I*V的二维数组(I为物品总个数,V为背包的总体积),可是有时候I和V可能很大,我们就需要很大的空间,甚至有可能超出范围,其实在只考虑最终价值不关心到底选了那几件物品时,上面转移方程的空间是可以压缩的。我们看到当考虑物品i时,我们用到的状态只与第i-1件物品有关,因此空间压缩的状态转移方程为:
当v<Ci时f[v]=f[v];(3)
当v>=Ci时f[v]=Max(f[v],f[v-Ci]+Wi);(4)
利用(4)的时候求解顺序很重要,要按v从大到小求,这样才能保证前面的状态不被覆盖。
这里说一下二进制拆分
假设原来某一种类的珠宝数量为N,我们可以把N拆成1,2,4,8,……,2^(k-1),N-2^k+1。这些拆分成的数字能够表示1~N之间的任何一个数。
这样,我们就把物品数减小为logN(以2为底,向上取整)。
以下是本题代码:

posted on 2012-08-14 16:32 小鼠标 阅读(1536) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2012年8月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜