先进先出队列式分支限界法求解0-1背包问题完整代码

以下是使用先进先出队列式分支限界法求解0-1背包问题的完整代码。代码中使用了 Python 3 编写。

import queue

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, items):
    if node.weight >= W:
        return 0
    else:
        bound = node.profit
        j = node.level + 1
        totweight = node.weight
        while (j < n) and (totweight + items[j][1] <= W):
            totweight += items[j][1]
            bound += items[j][0]
            j += 1
        if j < n:
            bound += (W - totweight) * (items[j][0] / items[j][1])
        return bound

def knapsack_bfs(n, W, items):
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    q = queue.Queue()
    u = Node(-1, 0, 0, 0)
    v = None
    maxprofit = 0
    u.bound = bound(u, n, W, items)
    q.put(u)
    while not q.empty():
        u = q.get()
        if u.level == -1:
            v = Node(0, 0, 0, 0)
        elif u.level == n - 1:
            continue
        v.level = u.level + 1
        v.weight = u.weight + items[v.level][1]
        v.profit = u.profit + items[v.level][0]
        if v.weight <= W and v.profit > maxprofit:
            maxprofit = v.profit
        v.bound = bound(v, n, W, items)
        if v.bound > maxprofit:
            q.put(v)
        v = Node(u.level + 1, u.profit, u.weight, 0)
        v.bound = bound(v, n, W, items)
        if v.bound > maxprofit:
            q.put(v)
    return maxprofit

# 测试代码
if __name__ == '__main__':
    n = 4
    W = 16
    items = [(40, 2), (30, 5), (50, 10), (10, 5)]
    maxprofit = knapsack_bfs(n, W, items)
    print("最大价值为:", maxprofit)

以上代码实现了先进先出队列式分支限界法求解0-1背包问题，其中 `Node` 类表示节点，`bound` 函数计算节点的上界，`knapsack_bfs` 函数使用 BFS 求解最大价值。在测试代码中，我们使用了一个包含 4 个物品、容量为 16 的背包和其价值、重量的列表来测试该算法。运行程序后，将输出最大价值为 90。