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

以下是使用队列式分支限界法解决01背包问题的Python代码:

import queue

class Node:
    def __init__(self, level, benefit, weight, bound):
        self.level = level
        self.benefit = benefit
        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:
        profit_bound = node.benefit
        j = node.level + 1
        total_weight = node.weight
        while j < n and total_weight + w[j] <= W:
            profit_bound += p[j]
            total_weight += w[j]
            j += 1
        if j < n:
            profit_bound += (W - total_weight) * p[j] / w[j]
        return profit_bound

def knapsack_bfs(n, W, p, w):
    pq = queue.PriorityQueue()
    root = Node(-1, 0, 0, 0)
    pq.put(root)
    max_profit = 0
    while not pq.empty():
        u = pq.get()
        if u.level == -1:
            v = Node(0, 0, 0, bound(root, n, W, p, w))
        elif u.level == n-1:
            continue
        else:
            v = Node(u.level+1, u.benefit + p[u.level+1], u.weight + w[u.level+1], bound(u, n, W, p, w))
        if v.weight <= W and v.benefit > max_profit:
            max_profit = v.benefit
        if v.bound > max_profit:
            pq.put(v)
        u.bound = bound(u, n, W, p, w)
        if u.bound > max_profit:
            pq.put(u)
    return max_profit

# example usage
n = 4
W = 10
p = [10, 40, 30, 50]
w = [5, 4, 6, 3]
print(knapsack_bfs(n, W, p, w)) # expected output: 90

在上面的代码中，我们定义了一个 `Node` 类，用于保存每个节点的信息。每个节点包含以下信息：

- `level`: 当前节点所处的层数（即将要决策的物品的编号）。
- `benefit`: 到达当前节点时已经获得的收益。
- `weight`: 到达当前节点时已经使用的背包容量。
- `bound`: 当前节点的最大可能收益（即上界）。

我们使用优先队列 `pq` 来存储待扩展的节点，并根据节点的上界值从大到小进行排序。在每次迭代时，我们从队列中取出上界最大的节点 `u`，并对其进行扩展。如果扩展后的节点 `v` 可以放入背包中，且其收益大于当前最大收益 `max_profit`，则更新 `max_profit`。同时，如果节点 `v` 的上界值大于当前最大收益 `max_profit`，将其加入队列中。另外，我们还需要对节点 `u` 进行上界计算，并将其加入队列中，以便在后续迭代中可能被扩展。

最终，函数返回的是背包能够容纳的最大收益。