首页 > 技术相关 > 0-1 背包问题详解 (3)

0-1 背包问题详解 (3)

2015年8月24日 发表评论 阅读评论

哪能搞法——分支界限

我们先把动态规划的想法放一下,退一步来看看这个问题。每一个物品都可能放或者不放,如果用一个决策树来表示的话,就得到这样一棵满二叉树:

fulltree

这对于 \(n\) 个物品就有 \(2^n\) 种放法,总共要计算 \(2^{n+1} – 2\) 个结点,当然是太多了。不过,有没有什么办法能让遍历的结点少一点呢?


比较直观的,至少有这么两个:

  • 重量超限的——如果一个结点重量超限,那再往上加东西的也不用看了。
  • 最下面一层的右侧打叉的结点——结果肯定和上一层一样,也不用再算一遍了。

还有吗?比如说,有些结点重量大而价值却很低,再怎么往上加东西也没有竞争力,能不能尽早找出这种“没有希望”的结点呢?

对于一些固定的物品,包包里能装走的价值是有一个上限的。包的大小是一定的,那么为了让总体价值最大,就要让单位重量的价值最大。怎么才能让单位重量的价值最大呢?我们把所有的物品按照价值与重量的比值(\(v_j / w_j\))由大到小排序,先尽量拣着重量小价值大的东西装,而把又重又不值钱的放在后面。

最后包包还没装满又放不下下一个物品怎么办呢?那我们就假装这个物品可以切开,然后把包包塞满。这样一来,现在得到的这个总价值就是一个上限,因为单位价值最高的那些已经都塞进来啦。

我们把物品排好顺序挨个考虑,如果有个结点已经考虑了前 \(i\) 个物品,得到的总价值是 \(V_0\),总重量是 \(W_0\);我们按照单位价值从大到小挨个往里放,放到第 \(k\) 个物品放不下了,这时候包里的总重量是
\[
\tilde{W} = W_0 + \sum_{j=i+1}^{k-1} w_j
\] 而总价值的上限就是
\[
V_{\rm bound} = \left(V_0 + \sum_{j=i+1}^{k-1} v_j \right) + \big(W – \tilde{W}\big)\cdot \frac{v_k}{w_k}
\] 其中前面一项是放进去的物品总价值,后面一项是把第 \(k\) 个物品切开后塞满包包的价值。

如果用 \(V_{\max}\) 表示已经出现过的最高价值,那遇到 \(V_{\rm bound} \leq V_{\max}\) 的结点就可以直接把它剪掉啦。

这个程序写出来可以是这样的:

简单解释一下,先对 vw 按照单位重量的价值排序,然后利用 bound 函数确定价值上限。如果价值上限超过了已经出现的最大价值,再分别计算加上当前物品和不加当前物品的两种情况,否则就跳过。

我们还拿前面的那个小例子来看,它执行过程可以用下面这个图来表示:
knapsack_tiny

显然这是一个深度优先搜索,图中每个结点分别列出了它的当前价值、当前重量和价值上限,红色结点表示重量超限,黄色结点表示价值上限不足,加粗的圈是最优解。这个树看起来比上面那个小多了吧!

如果包包大一点,效果就更明显了,比如这个有 15 个物品的包包,它的搜索过程是这样的(点击看大图):

knapsack_15

看看我们剪掉了多少红圈黄圈!看起来很不错,让我们来试试前面的那些大包包…… 诶怎么回事……

好吧递归太深了……我们可以加大递归深度:

在 Windows 下面递归深度除了受 recursion limit 约束,还受栈空间限制,所以这里用 thread 来设定栈空间,而它只对新建的线程有效。如果不扩大栈空间,2000 个项目还可以,10000 个就不行了。

当然,所有的递归都是可以解开的,为什么非要用递归呢!直接把后面待处理的结点压进栈里不就行了吗,当然要注意压栈的顺序变了:

那个有 10000 个元素的大包包也完全不在话下,瞬间就可以解开啦!

更多算法内容请见《算法拾珠》

%d 博主赞过: