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

哪能搞法——动态规划再试

不知道有没有读者试过了这个大包包,我试了一下,在我的 2.30GHz i5 5300U 上,这个函数用 cPython 跑了…… 1632.07 秒,将近半个小时。照这个搞法,每次那个包有多大,就得搞出多少项。那个包的大小可是个任意数啊?这 $ W$ 比 $ 2^n$ 大都说不定呢?

咱们再来琢磨琢磨这个事儿。看看刚才那个最小的例子,也就是背包总重不超过 16,有这样几件物品:

物品 价值 重量
0 30 4
1 20 5
2 40 10
3 10 3

我们产生的 $ F$ 是这样的:

[0, 0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 50, 50, 50]
[0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 70, 70, 70]
[0, 0, 0, 10, 30, 30, 30, 40, 40, 50, 50, 50, 60, 60, 70, 70, 70]

你什么感觉,是不是怎么这么多重复项??我们真的需要保留这么多重复项吗?

动态规划说到底,是把 $ n$ 个对象的情况化归成 $ n-x$ 个对象的子问题。我们这个 $ F$ 里面实际的信息量是什么呢?

  • 第一轮,加入 0 号物品,可以用 4 的重量做到 30 的价值。
  • 第二轮,加入 1 号物品,可以用 5 的重量做到 20 的价值——慢着,我们前一轮已经用 4 的重量做到的 30 的价值,你用 5 才做到 20,这完全没有意义嘛!所以它并没有表现在 $ F$ 中。然而如果同时加入 0 号和 1 号物品,我们就可以用 9 的重量做到 50 的价值。这是一个新的信息。
  • 第三轮,再加入 2 号物品,同理,我们只有在重量达到 14,价值达到 70 的时候才是一个新的信息。
  • 第四轮,我们用 3 的重量就做到了 10 的价值,而以前 3 的重量什么也做不出。那么这也是一个新信息。

看出什么端倪了么?我们其实只需要保留有信息量的部分,即用最少的重量做到某一个价值的时刻。如果有两个状态 $ (V_1, W_1)$ 和 $ (V_2, W_2)$,使得 $ W_2 > W_1$,但 $V_2 \leq V_1$,也就是说状态 2 的重量大但价值不高的话,那么就说明状态 2 是占劣势而无需继续考虑的。如果能把这些劣势状态通通舍弃,我们要处理的数据量(通常)可以大大缩减。

道理理解了,如何实现呢?我们可以用元组 (tuple) 来表示价值和重量,并把它们按顺序排起来。仍以上面的例子来说:

  • 最初我们什么也没有,只有一个元组(0, 0)
  • 我们试着加上第 0 号元素,得到了(30, 4)。与最初的元组合并,于是变成了(0, 0), (30, 4)
  • 再试着对每一种情况加上第 1 号元素,得到了(20, 5), (50, 9)。与上一轮的元组合并,由于(20, 5)处于劣势被舍弃了。合并的结果是(0, 0), (30, 4), (50, 9)
  • 继续做这个操作,加上第 2 号元素得到(40, 10), (70, 14), (90, 19)。最后一个由于超限被舍弃了,再于上一轮合并,得到(0, 0), (30, 4), (50, 9), (70, 14)
  • 最后一轮再加上去,终于得到了最终结果(0, 0), (10, 3), (30, 4), (40, 7), (50, 9), (60, 12), (70, 14)。

deque

我的这个实现为了合并的方便使用了 python 中的双向链表 collections.deque。它不但写起来方便,而且实测下来比直接用列表和指针还要快一些(原因未知):

#!/usr/bin/env python3

from collections import deque
import sys
INF = float("inf")

def knapsack(vw, limit, n):
    vw = sorted(vw, key=lambda x : x[1], reverse=True)  # Accelerate
    A = deque([(0, 0)])

    for i in range(0, n):
        B = deque()       #  find all possiblities after adding one new item
        for item in A:
            if item[1] + vw[i][1] > limit:  # A is sorted
                break
            B.append((item[0] + vw[i][0], item[1] + vw[i][1]))

        level, merge = -1, deque()  # the bar keeps going up
        while A or B:    # merging the two queues
            ia, ib = A[0][1] if A else INF, B[0][1] if B else INF
            x = A.popleft() if (ia < ib) else B.popleft()
            if x[0] > level:
                merge.append(x)
                level = x[0]
        A = merge
    return A[-1]

if __name__ == "__main__":
    with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f:
        limit, n = map(int, f.readline().split())
        vw = [tuple(map(int, ln.split())) for ln in f.readlines()]
    A = knapsack(vw, limit, n)
    print("Max value:", A[0], "Total weight:", A[1])

用这个来解决大包包是轻轻松松啦!在我机器上的运行时间大约只有半秒钟,真的可谓是秒杀!我们这个算法的时间复杂度是 $O(ns)$,其中 $s$ 是上面列出来的独立状态数。这个状态数既不可能超过 $W$,也不可能超过 $2^n$。对于分布比较均匀的背包物品来说,这个方法还是相当奏效的。

也许你注意到了第 8 行有一条奇怪的排序……这个算法虽然对数据的顺序本身没有要求,但是我发现,如果对数据按照重量从大到小排序,速度比乱序提升了大约四倍。我也试过其他的排序方法,比如按照价值与重量的比值,但在这个特定例子上均不太理想。

但是呢……遇到更大的包包怎么办……我跑了一下 cPython 需要 677.3 秒…… PyPy 快一些需要 65 秒左右。

其实,我们并不需要在动态规划这一棵树上吊死的呢…… 且听下回分解

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

One thought on “0-1 背包问题详解 (2)

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据