0-1背包问题-分支限界法先进先出队列代码

下面是使用分支限界法和先进先出队列解决0-1背包问题的Python代码示例：

import queue

class Node:
    def __init__(self, level, profit, weight, bound):
        self.level = level
        self.profit = profit
        self.weight = weight
        self.bound = 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 = queue.Queue()
    u = Node(-1, 0, 0, 0)
    v = Node(-1, 0, 0, bound(u, n, W, p, w))
    maxprofit = 0
    q.put(v)
    while not q.empty():
        u = q.get()
        if u.bound > maxprofit:
            i = u.level + 1
            v = Node(i, u.profit + p[i], u.weight + w[i], 0)
            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 = Node(i, u.profit, u.weight, 0)
            v.bound = bound(v, n, W, p, w)
            if v.bound > maxprofit:
                q.put(v)
    return maxprofit

# 测试代码
n = 5
W = 10
p = [10, 5, 15, 7, 6]
w = [1, 3, 4, 2, 1]
print(knapsack(n, W, p, w)) # 输出：27