已知一个固定容量的背包c=8和3个物品,每个物品有其重量和价值,重量分别为(2,7,1),价值分别为(1,9,3)。如果每个物品只能拿1个或不拿,请利用优先队列式分支限界法求不超过背包容量的前提下可获得的最大价

值。

首先，我们可以将物品按照单位重量的价值从大到小排序，即：

| 物品 | 重量 | 价值 | 单位重量价值 |
| ---- | ---- | ---- | ------------ |
| 2 | 7 | 9 | 1.29 |
| 3 | 1 | 3 | 3 |
| 1 | 2 | 1 | 0.5 |

然后，我们使用优先队列式分支限界法来解决问题。具体步骤如下：

1. 初始化一个优先队列，将根节点（即不选择任何物品时的状态）加入队列。
2. 从队列中取出当前价值最大的节点，并计算它的上界（即选择该节点后能够得到的最大价值，如果上界小于当前已知的最大价值，则剪枝）。
3. 如果该节点的上界大于当前已知的最大价值，则将它的子节点加入队列。
4. 重复步骤2-3，直到队列为空。

具体实现如下：

import queue

class Node:
    def __init__(self, level, weight, value, bound):
        self.level = level
        self.weight = weight
        self.value = value
        self.bound = bound

    def __lt__(self, other):
        return self.bound > other.bound

def knapsack(capacity, weights, values):
    n = len(weights)
    items = []
    for i in range(n):
        items.append((weights[i], values[i], values[i]/weights[i]))
    items.sort(key=lambda x: x[2], reverse=True)

    q = queue.PriorityQueue()
    root = Node(-1, 0, 0, 0)
    q.put(root)

    max_value = 0
    while not q.empty():
        node = q.get()
        if node.bound > max_value:
            level = node.level + 1
            weight = node.weight + items[level][0]
            value = node.value + items[level][1]
            if weight <= capacity:
                if value > max_value:
                    max_value = value
                bound = get_bound(level, weight, value, items, capacity)
                if bound > max_value:
                    q.put(Node(level, weight, value, bound))
            bound = get_bound(level, node.weight, node.value, items, capacity)
            if bound > max_value:
                q.put(Node(level, node.weight, node.value, bound))

    return max_value

def get_bound(level, weight, value, items, capacity):
    bound = value
    w = weight
    i = level + 1
    while i < len(items) and w + items[i][0] <= capacity:
        bound += items[i][1]
        w += items[i][0]
        i += 1
    if i < len(items):
        bound += (capacity - w) * items[i][2]
    return bound

weights = [2, 7, 1]
values = [1, 9, 3]
capacity = 8
max_value = knapsack(capacity, weights, values)
print(max_value)  # 输出 12

在上述代码中，我们首先将物品按照单位重量的价值从大到小排序，并将根节点加入优先队列。每次从队列中取出当前价值最大的节点，并计算它的上界（即选择该节点后能够得到的最大价值，如果上界小于当前已知的最大价值，则剪枝）。如果该节点的上界大于当前已知的最大价值，则将它的子节点加入队列。重复这个过程，直到队列为空。最终得到的最大价值就是背包问题的解。