背包问题.doc
《背包问题.doc》由会员分享,可在线阅读,更多相关《背包问题.doc(2页珍藏版)》请在三一文库上搜索。
1、转自:背包问题九讲01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是ci,价值是wi。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:fiv=maxfi-1v,fi-1v-ci+wi这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题
2、。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为fi-1v;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-ci的背包中”,此时能获得的最大价值就是fi-1v-ci再加上通过放入第i件物品获得的价值wi。优化空间复杂度:以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1.N,每次算出来二维数组fi0.V的所有值。那么,如果只用一个数组f0.V,能不能保证第i次循环结束后fv中表示的就是我们定义的状态fiv呢?fiv是由
3、fi-1v和fi-1v-ci两个子问题递推而来,能否保证在推fiv时(也即在第i次主循环中推fv时)能够得到fi-1v和fi-1v-ci的值呢?事实上,这要求在每次主循环中我们以v=V.0的顺序推fv,这样才能保证推fv时fv-ci保存的是状态fi-1v-ci的值。伪代码如下:for i=1.N for v=V.0 fv=maxfv,fv-ci+wi;其中的fv=maxfv,fv-ci一句恰就相当于我们的转移方程fiv=maxfi-1v,fi-1v-ci,因为现在的fv-ci就相当于原来的fi-1v-ci。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了fiv由fiv-ci推知,与本题意
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 背包 问题
链接地址:https://www.31doc.com/p-11042219.html