讨论 / 给看不懂标程的朋友的一点提示
cotton 2013-07-05 01:29:00
点我顶贴 收藏 删除
01背包问题,如果直接解决,是一个NP的问题。对于一共的N件物品,每一件都有两种决策:0/1(不取或取)。那么,一共需要进行N次决策,时间复杂度为2的N次方。转化为直观的表示方式,就是有一颗深度为N的二叉树(可能不是完全二叉树)。最终的最优解,就是遍历整棵树后,使F[ n , v ]的值最大 (表示进行N次决策后,占用V的体积能得到的最大价值,不一定为恰好)。

现在回到DP(暴搜没前途啊)。首先假设你已经看过《背包九讲》,再回来把DP与搜索树建立联系。对于每一次决策后,我们都能得到一组值:F[ i, j] I 表示进行了I次决策,J表示占用了J 的体积。最终获得了F[i,j]的收益。这么考虑的话,很显然,就能得到最优子结构的性质

:如果最终能得到Fmax[ n, v ] ,那对于每一组i,j 必定 F[i,j]=Fmax[i,j]。因此,在遍历树的时候,如果两种决策有相同的i,j 那我们可以取出两者中的最大值,另外一种就被无情的抛弃了-_- 。这样,对于每一组的i,j 我们可以方便的按如下方程求出:

F[i,j]=max( F[i-1,j] , f[i-1][j-volume[i]] + value[i] ) 按照这个方程,就能方便地求出最优解

再分析一下这个方程。他符合之前说的两种决策:选取物品i,或不选。最终的结果,是我们能在O(1)的时间内,判定对于体积j,是否应当选取第i件物品。 我们在这里作出了最优的选择。那被我们抛弃的选择呢?他很可能是次优解,第三优解,无论怎样,他都对我们本题求前K优解,起到了重要的作用!

那么,本题的算法,就水到渠成了。设数组[ i , j , p ]。表示对于一组 i,j, F[i,j,p] 为其第P优的决策。那么,上文的max操作,就需要稍加扩展,变为对两个队列的合并(一种决策的第a1优解很可能是总体的第a2优解)。毋庸置疑,这两个队列是有序的,将其合并即可完成本次决策。代价,则从O(1) 涨到了O(k) ,总的时间复杂度由O(vn) 升至O(vnk) 刚好多了一维。

摘自http://hi.baidu.com/letusdo/blog/item/708f6d276a85d119908f9d68.html

#1 liusikai@2013-07-05 01:29:00
回复 删除
分析的很到位!!!值得一看。开始接触这个题目的时候不知所措,对于大家的分析的更是云里雾里。但是,此时我们不能灰心,多看几遍再自己多想几遍。对于新知识大家都是慢慢接受它并深层次理解它。呵呵。。。。
查看更多回复
提交回复