求解0/1背包箱问题。分别用先进先出队列分支限界法和优先队列分支限界法实现。

0/1背包问题是经典的NP完全问题，分支限界法是解决该问题的一种有效方法。下面分别介绍使用先进先出队列和优先队列的分支限界法实现0/1背包问题。

先进先出队列分支限界法：

步骤1：将物品按照单位重量的价值从大到小排序，即价值密度从大到小排序。

步骤2：初始化队列Q，并将根节点放入队列中。

步骤3：从队列中取出一个节点，并计算该节点的上界。

步骤4：如果上界小于当前最优解，则退出循环；否则，扩展该节点，生成两个子节点，一个选择该物品，一个不选择该物品，并将子节点插入队列中。

步骤5：重复步骤3和步骤4，直到队列为空。

优先队列分支限界法：

步骤1：将物品按照单位重量的价值从大到小排序，即价值密度从大到小排序。

步骤2：初始化优先队列P，并将根节点放入队列中。

步骤3：从队列中取出一个节点，并计算该节点的上界。

步骤4：如果上界小于当前最优解，则退出循环；否则，扩展该节点，生成两个子节点，一个选择该物品，一个不选择该物品，并将子节点插入队列中。

步骤5：重复步骤3和步骤4，直到队列为空。

两种方法的主要区别在于队列的不同，先进先出队列按照先进先出的顺序取出节点，而优先队列则按照节点的上界进行排序，每次取出上界最小的节点进行扩展。

下面是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 knapsack_BFS(profits, weights, capacity):
    n = len(profits)
    q = queue.Queue()
    root = Node(-1, 0, 0, 0)
    q.put(root)
    max_profit = 0

    while not q.empty():
        node = q.get()

        if node.level == n-1:
            continue

        level = node.level + 1
        profit = node.profit + profits[level]
        weight = node.weight + weights[level]

        if weight <= capacity and profit > max_profit:
            max_profit = profit

        bound = get_bound(level, n, weights, profits, capacity, weight, profit)

        if bound > max_profit:
            q.put(Node(level, profit, weight, bound))

        bound = get_bound(level, n, weights, profits, capacity, node.weight, node.profit)

        if bound > max_profit:
            q.put(Node(level, node.profit, node.weight, bound))

    return max_profit

def get_bound(level, n, weights, profits, capacity, weight, profit):
    if weight >= capacity:
        return 0

    bound = profit
    j = level + 1
    total_weight = weight

    while j < n and total_weight + weights[j] <= capacity:
        bound += profits[j]
        total_weight += weights[j]
        j += 1

    if j < n:
        bound += (capacity - total_weight) * profits[j] / weights[j]

    return bound

profits = [10, 5, 15, 7, 6, 18, 3]
weights = [2, 3, 5, 7, 1, 4, 1]
capacity = 15
print(knapsack_BFS(profits, weights, capacity))

优先队列分支限界法实现：

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 knapsack_PQ(profits, weights, capacity):
    n = len(profits)
    pq = queue.PriorityQueue()
    root = Node(-1, 0, 0, 0)
    pq.put(root)
    max_profit = 0

    while not pq.empty():
        node = pq.get()

        if node.level == n-1:
            continue

        level = node.level + 1
        profit = node.profit + profits[level]
        weight = node.weight + weights[level]

        if weight <= capacity and profit > max_profit:
            max_profit = profit

        bound = get_bound(level, n, weights, profits, capacity, weight, profit)

        if bound > max_profit:
            pq.put(Node(level, profit, weight, bound))

        bound = get_bound(level, n, weights, profits, capacity, node.weight, node.profit)

        if bound > max_profit:
            pq.put(Node(level, node.profit, node.weight, bound))

    return max_profit

def get_bound(level, n, weights, profits, capacity, weight, profit):
    if weight >= capacity:
        return 0

    bound = profit
    j = level + 1
    total_weight = weight

    while j < n and total_weight + weights[j] <= capacity:
        bound += profits[j]
        total_weight += weights[j]
        j += 1

    if j < n:
        bound += (capacity - total_weight) * profits[j] / weights[j]

    return bound

profits = [10, 5, 15, 7, 6, 18, 3]
weights = [2, 3, 5, 7, 1, 4, 1]
capacity = 15
print(knapsack_PQ(profits, weights, capacity))