用分支限界法解决背包问题

分支限界法是一种解决问题的算法思想，可以用来解决背包问题。下面是使用分支限界法解决背包问题的步骤：

1. 定义问题：背包问题是一个经典的优化问题，给定一组物品和一个背包的容量，每个物品有自己的重量和价值，要求在不超过背包容量的情况下，选择一些物品放入背包，使得背包中物品的总价值最大。

2. 创建优先队列或栈：在分支限界法中，需要使用优先队列或栈来存储待扩展的结点。每个结点表示一个状态，包括已选择的物品、剩余的容量和当前的价值。

3. 初始化根结点：将根结点初始化为初始状态，即没有选择任何物品，背包的剩余容量为背包的总容量，当前的价值为0。

4. 扩展结点：从优先队列或栈中取出一个结点进行扩展。对于每个结点，可以选择放入下一个物品或不放入。如果放入物品后仍然满足背包容量的限制，则计算放入物品后的总价值，并将新的结点加入优先队列或栈中。

5. 剪枝操作：在扩展结点时，可以进行剪枝操作来减少搜索空间。例如，如果当前结点的价值已经小于已知的最优解，则可以剪枝。

6. 更新最优解：在扩展结点时，如果找到了一个更优的解，则更新最优解。

7. 终止条件：当优先队列或栈为空时，表示已经搜索完所有的结点，算法终止。此时，最优解即为找到的最优解。

下面是一个使用分支限界法解决背包问题的示例代码：

from queue import PriorityQueue

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

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

def knapsack(items, capacity):
    n = len(items)
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    pq = PriorityQueue()
    v = 0
    w = 0
    max_value = 0

    u = Node(-1, 0, 0, 0)
    pq.put(u)

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

        if u.bound > max_value:
            level = u.level + 1
            value = u.value + items[level][1]
            weight = u.weight + items[level][0]

            if weight <= capacity and value > max_value:
                max_value = value

            bound = compute_bound(items, capacity, level, value, weight)
            if bound > max_value:
                v = Node(level, value, weight, bound)
                pq.put(v)

            value = u.value
            weight = u.weight
            bound = compute_bound(items, capacity, level, value, weight)
            if bound > max_value:
                v = Node(level, value, weight, bound)
                pq.put(v)

    return max_value

def compute_bound(items, capacity, level, value, weight):
    if weight >= capacity:
        return 0

    bound = value
    j = level + 1
    totweight = weight

    while j < len(items) and totweight + items[j][0] <= capacity:
        totweight += items[j][0]
        bound += items[j][1]
        j += 1

    if j < len(items):
        bound += (capacity - totweight) * items[j][1] / items[j][0]

    return bound

items = [(2, 40), (3, 50), (5, 100), (9, 95), (7, 30)]
capacity = 15

max_value = knapsack(items, capacity)
print("Max value: ", max_value)