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

def branch_bound_knapsack(weights, values, capacity):
    class Node:
        def __init__(self, level, weight, value, bound):
            self.level = level
            self.weight = weight
            self.value = value
            self.bound = bound

    def bound(node):
        if node.weight >= capacity:
            return 0
        bound = node.value
        j = node.level + 1
        total_weight = node.weight
        while j < n and total_weight + weights[j] <= capacity:
            total_weight += weights[j]
            bound += values[j]
            j += 1
        if j < n:
            bound += (capacity - total_weight) * values[j] / weights[j]
        return bound

    n = len(weights)
    max_value = 0
    Q = []
    root = Node(-1, 0, 0, 0)
    Q.append(root)
    while Q:
        node = Q.pop(0)
        if node.level == n - 1:
            continue
        left = Node(node.level + 1, node.weight, node.value, 0)
        left.bound = bound(left)
        if left.bound > max_value:
            Q.append(left)
        right = Node(node.level + 1, node.weight + weights[node.level + 1], node.value + values[node.level + 1], 0)
        right.bound = bound(right)
        if right.weight <= capacity and right.value > max_value:
            max_value = right.value
        if right.bound > max_value:
            Q.append(right)
    return max_value

# 解释以上代码内容：
以上代码是一个使用分支限界法解决背包问题的算法。背包问题是一个经典的组合优化问题，目标是在给定的一组物品中选择一些物品放入背包中，使得物品的总价值最大，同时不能超过背包的容量。

该算法使用了一个 Node 类来表示搜索树的节点，每个节点包含了当前节点的层数、当前节点已选取的物品总重量和总价值以及当前节点的上界。

在算法的主循环中，首先创建一个根节点，并将其加入到一个队列 Q 中。然后，循环从队列中取出一个节点，如果该节点是叶子节点，则跳过。否则，根据当前节点创建两个子节点，一个是选择当前物品的子节点，另一个是不选择当前物品的子节点。然后，计算这两个子节点的上界，并将上界大于当前最大价值的子节点加入到队列 Q 中。如果选择当前物品的子节点的总重量不超过背包容量，并且其总价值大于当前最大价值，则更新当前最大价值。

最后，返回最大价值作为算法的结果。

算法的时间复杂度是 O(2^n)，其中 n 是物品的个数。因为每个物品都有两种选择，所以搜索树的节点数是 2^n。算法的空间复杂度是 O(n)，因为需要保存每个节点的信息。