使用队列式分支限界法解决01背包问题Python实现

以下是使用队列式分支限界法解决01背包问题的Python实现：

from queue import PriorityQueue

class Node:
    def __init__(self, level, profit, weight, bound):
        self.level = level
        self.profit = profit
        self.weight = weight
        self.bound = bound

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

def bound(node, n, W, p, w):
    if node.weight >= W:
        return 0
    else:
        result = node.profit
        j = node.level + 1
        totweight = node.weight
        while j <= n and totweight + w[j] <= W:
            totweight += w[j]
            result += p[j]
            j += 1
        if j <= n:
            result += (W - totweight) * p[j] / w[j]
        return result

def knapsack(n, W, p, w):
    q = PriorityQueue()
    v = Node(0, 0, 0, 0)
    u = Node(0, p[1], w[1], 0)
    maxprofit = 0
    u.bound = bound(u, n, W, p, w)
    q.put(u)
    while not q.empty():
        u = q.get()
        if u.bound > maxprofit:
            v.level = u.level + 1
            v.weight = u.weight + w[v.level]
            v.profit = u.profit + p[v.level]
            if v.weight <= W and v.profit > maxprofit:
                maxprofit = v.profit
            v.bound = bound(v, n, W, p, w)
            if v.bound > maxprofit:
                q.put(v)
            v.weight = u.weight
            v.profit = u.profit
            v.bound = bound(v, n, W, p, w)
            if v.bound > maxprofit:
                q.put(v)
    return maxprofit

# Sample usage
n = 5
W = 10
p = [0, 40, 50, 100, 95, 30]
w = [0, 2, 3, 5, 4, 8]
print(knapsack(n, W, p, w)) # Output: 235

在这个实现中，我们使用了Python的`PriorityQueue`数据结构来维护未扩展节点的队列。在每次从队列中获取节点时，我们计算其上界，如果上界大于当前已知的最大收益，则将其扩展并将其子节点加入队列中。我们通过排序队列来确保我们总是优先考虑具有最高上界的节点。