利用队列分支限界法求解0/1背包问题源码

以下是Python实现的0/1背包问题的队列分支限界法：

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.ratio = value / weight

    def __lt__(self, other):
        return self.ratio > other.ratio


def knapsack(items, capacity):
    items.sort()
    max_value = 0
    queue = [(0, 0, 0)]
    while queue:
        level, value, weight = queue.pop(0)
        if weight > capacity:
            continue
        if level == len(items):
            max_value = max(max_value, value)
            continue
        item = items[level]
        queue.append((level + 1, value + item.value, weight + item.weight))
        queue.append((level + 1, value, weight))

    return max_value

其中，Item类用于表示物品，包含重量、价值和价值重量比三个属性。
knapsack函数是核心函数，其中items是物品列表，capacity是背包容量。
算法先将物品按照价值重量比从大到小排序，然后用一个队列保存待扩展的节点，每次从队首取出节点进行扩展，如果重量超出容量则跳过，如果扩展到最后一层则更新最大价值，否则将两个子节点（选中当前物品或不选）加入队列。
最终返回最大价值。