使用队列式分支限界法解决01背包问题Python完整代码

下面是使用队列式分支限界法解决01背包问题的Python完整代码：

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

    def __lt__(self, other):
        return self.cost < other.cost

def bound(u, n, W, items):
    if u.weight >= W:
        return 0
    
    profit_bound = u.value
    j = u.level + 1
    totweight = u.weight
    
    while j < n and totweight + items[j].weight <= W:
        totweight += items[j].weight
        profit_bound += items[j].value
        j += 1

    if j < n:
        profit_bound += (W - totweight) * items[j].cost

    return profit_bound

def knapsack(W, items, n):
    items.sort(reverse=True)
    q = []
    u = Item(0, 0)
    v = Item(0, 0)
    maxProfit = 0
    u.level = -1
    q.append(u)

    while len(q) > 0:
        u = q.pop(0)

        if u.level == -1:
            v.level = 0

        if u.level == n-1:
            continue

        v.level = u.level + 1
        v.weight = u.weight + items[v.level].weight
        v.value = u.value + items[v.level].value

        if v.weight <= W and v.value > maxProfit:
            maxProfit = v.value

        v.bound = bound(v, n, W, items)

        if v.bound > maxProfit:
            q.append(v)

        v = Item(0, 0)
        v.weight = u.weight
        v.value = u.value
        v.bound = bound(v, n, W, items)

        if v.bound > maxProfit:
            q.append(v)

    return maxProfit

# 测试代码
W = 50
items = [Item(10, 60), Item(20, 100), Item(30, 120)]
n = len(items)

print("Maximum profit:", knapsack(W, items, n))

输出结果为：

Maximum profit: 220

其中，`Item` 类表示一个物品，包含重量、价值和单位重量价值（即性价比）三个属性。`bound` 函数用于计算当前节点的最大可能收益，采用贪心策略计算。`knapsack` 函数是主要的分支限界算法实现，使用队列来存储待扩展的节点，每次从队首取出一个节点进行扩展。在扩展过程中，如果发现子节点的上界大于当前的最大收益，则将其加入队列中。最终返回的是最大收益。