解0/1背包箱问题。分别用fifo队列分支限界法实现。

0/1背包问题是一个常见的动态规划问题，可以用分支限界法来解决。下面分别介绍使用FIFO队列的分支限界法的实现。

FIFO队列分支限界法的实现：

1. 将所有的物品按照单位价值（即每个物品的价值除以重量）从大到小排序。

2. 定义一个FIFO队列，将初始节点（即没有任何物品被选中的情况）加入队列中。

3. 当队列不为空时，取出队首节点进行扩展，并将得到的子节点按照价值非递增的顺序插入FIFO队列中。

4. 当队首节点对应的背包重量达到了背包容量或者队首节点已经没有子节点可扩展时，将队首节点从队列中删除。

5. 重复执行3-4步骤，直到队列为空。

以下是使用FIFO队列分支限界法的Python实现代码：

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:
        profit_bound = node.profit
        j = node.level + 1
        totweight = node.weight
        while j < n and totweight + w[j] <= W:
            totweight += w[j]
            profit_bound += p[j]
            j += 1
        if j < n:
            profit_bound += (W - totweight) * p[j] / w[j]
        return profit_bound

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

p = [10, 5, 15, 7, 6, 18, 3]
w = [2, 3, 5, 7, 1, 4, 1]
W = 15
print(knapsack(p, w, W))

其中，Node表示一个节点，包括level（节点所在的层数）、profit（当前已选中的物品总价值）、weight（当前已选中的物品总重量）和bound（该节点的价值上界）四个属性。bound函数用于计算节点的价值上界，即该节点的最大可能价值。knapsack函数用于求解0/1背包问题，其中p、w、W分别表示物品的价值、重量和背包容量。