编辑代码

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight

def knapsack_branch_and_bound(max_weight, items):
    # 用于存储最佳解决方案和其价值
    best_value = 0
    best_combination = []

    # 按单位重量价值排序
    items.sort(key=lambda x: x.ratio, reverse=True)

    # 辅助函数：计算给定节点的上界
    def bound(node, current_weight, current_value):
        if current_weight >= max_weight:
            return 0
        value_bound = current_value
        j = node
        total_weight = current_weight
        while j < len(items) and total_weight + items[j].weight <= max_weight:
            total_weight += items[j].weight
            value_bound += items[j].value
            j += 1
        if j < len(items):
            value_bound += (max_weight - total_weight) * items[j].ratio
        return value_bound

    # 辅助函数：递归地探索节点
    def explore_node(node, current_weight, current_value, current_combination):
        nonlocal best_value, best_combination

        if node == len(items) or current_weight > max_weight:
            return

        if current_value > best_value:
            best_value = current_value
            best_combination = current_combination.copy()

        # 探索包含当前节点的情况
        next_node = node + 1
        if current_weight + items[node].weight <= max_weight:
            current_combination.append(items[node])
            explore_node(next_node, current_weight + items[node].weight, current_value + items[node].value, current_combination)
            current_combination.pop()

        # 探索不包含当前节点的情况（只有在下一个节点的上界比当前最佳值高时）
        if bound(next_node, current_weight, current_value) > best_value:
            explore_node(next_node, current_weight, current_value, current_combination)

    # 调用递归函数
    explore_node(0, 0, 0, [])

    return best_value, best_combination

# 示例数据
max_weight = 50
items = [Item(60, 10), Item(100, 20), Item(120, 30)]

# 调用函数并输出结果
knapsack_branch_and_bound(max_weight, items)