0-背包问题分支限界法代码

以下是0-背包问题的分支限界法代码：

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.ratio = value / weight  # 计算性价比

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

def knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)  # 按性价比排序

    n = len(items)
    queue = []
    best_value = 0  # 最优解

    # 根节点
    root = Node(-1, 0, 0, 0)
    queue.append(root)

    while queue:
        node = queue.pop(0)

        # 到达叶子节点
        if node.level == n-1:
            if node.value > best_value:
                best_value = node.value

        else:
            # 左儿子节点：选择该物品
            left = Node(node.level+1,
                        node.weight + items[node.level+1].weight,
                        node.value + items[node.level+1].value,
                        0)

            if left.weight <= capacity:
                left.bound = bound(left, items, capacity)
                if left.bound > best_value:
                    queue.append(left)
                if left.value > best_value:
                    best_value = left.value

            # 右儿子节点：不选该物品
            right = Node(node.level+1,
                         node.weight,
                         node.value,
                         0)
            right.bound = bound(right, items, capacity)
            if right.bound > best_value:
                queue.append(right)

    return best_value

# 计算上界
def bound(node, items, capacity):
    if node.weight >= capacity:
        return 0

    bound = node.value
    j = node.level + 1
    total_weight = node.weight

    while j < len(items) and total_weight + items[j].weight <= capacity:
        bound += items[j].value
        total_weight += items[j].weight
        j += 1

    if j < len(items):
        bound += (capacity - total_weight) * items[j].ratio

    return bound

其中，`Item` 表示一个物品，包含重量、价值和性价比三个属性。`Node` 表示一个节点，包含当前层数、已装载物品的重量、已装载物品的价值和上界四个属性。`knapsack` 函数实现了分支限界法，并返回了最优解。`bound` 函数用于计算上界，即估算从当前节点出发可以得到的最大价值。