Python解决0-1背包问题

背包问题是一个经典的问题,其有多个变种,本节要解决的是 0-1 背包问题。

题目如下,给定一个背包,其容量为 v,现在有 n 个物品,它们的体积分别为 e1、e2、…、en。现在挑选任意多个物品放入背包内,要求它们的体积和不能超过背包容量 v,并且希望尽量接近 v,如背包容量为 100,那么物品体积和为 99 的方案就比物品体积和为 98 的方案要好,当然最好是体积和等于背包容量 v。我们就是要找到这个最优的物品组合。

为了说明该类问题的解决方案,我们设定了一个特殊的场景,在该场景中,背包容量为 10,物品有 4 个,它们的容量分别为 1、3、6、8。现在我们需要计算出这个最优的物品组合。

最简单的方法就是列出所有的排列组合,看看它们是否满足条件。由于有 4 个物体,每个物体有两个可能选项,放入背包或者不放入背包。下面为实现代码:
goods_list = [1, 3, 6, 8]
def resolve_bag(bag_volume, goods_list):
    biggest_valid_vol = 0
    biggest_valid_selection = []
    goods_num = len(goods_list)
    candidate_num = 1 << goods_num
    for candidate in range(candidate_num):
        selection_decision = []
        for x in range(goods_num):
            if (candidate & 1) == 1:
                selection_decision.append(True)
            else:
                selection_decision.append(False)
            candidate = candidate >> 1
        current_vol = 0
        for x in range(goods_num):
            if selection_decision[x] == True:
                current_vol = current_vol + goods_list[x]
        if current_vol <= bag_volume and current_vol > biggest_valid_vol:
            biggest_valid_vol = current_vol
            biggest_valid_selection = selection_decision
    result = [goods_list[x] for x in range(goods_num) if biggest_valid_selection[x] == True]
    print(result)
resolve_bag(10, goods_list)
运行结果:
[1, 3, 6]

但是该程序的运行效率比较低下,其枚举了所有的组合。对于这个过程,可以用决策树来表示。

我们可以用两个信息来描述每个状态,一个是背包的剩余空间,一个是没有放入背包的物品。如初始状态就是有 10 个剩余空间,没有放入背包的物品体积依次为 1、3、6、8。然后我们对于所有的物品,从右往左,依次决定是否放入背包。如将体积为 8 的物品放入背包,那么就得到这样一个状态,其背包剩余空间是 2,没有放入到背包的物品容量是 1、3、6。如果决定不将体积为8的放入背包,那么就得到这样一个状态,剩余空间为 10,没有放入背包的物品体积为 1、3、6。

除掉一些明显不太可能出现的状态,可以得到如图1所示的一个状态图。

背包问题的状态图
图1:背包问题的状态图

最后找到右下角的这个状态,剩余空间为 0,即将背包完全装满了。这就是我们的终极状态了。