import randomimport timeimport matplotlibpyplot as pltimport numpy as np# 生成随机的物品重量和价值def generate_itemsn weights = randomrandint1 10 for _ in rangen values = randomrandint10 50 for _ in rangen

在蛮力法、回溯法和分支限界法的函数中，添加一个变量来保存最优解，并在函数结束时返回该最优解即可。

以下是修改后的代码：

# 蛮力法求解0/1背包问题
def brute_force_knapsack(weights, values, capacity):
    n = len(weights)
    max_value = 0
    best_items = []
    for i in range(2 ** n):
        current_weight = 0
        current_value = 0
        current_items = []
        for j in range(n):
            if (i >> j) & 1:
                current_weight += weights[j]
                current_value += values[j]
                current_items.append(j)
        if current_weight <= capacity and current_value > max_value:
            max_value = current_value
            best_items = current_items
    return max_value, best_items


# 回溯法求解0/1背包问题
def backtrack_knapsack(weights, values, capacity):
    def backtrack(i, current_weight, current_value, current_items):
        nonlocal max_value, best_items
        if current_weight > capacity:
            return
        if current_value > max_value:
            max_value = current_value
            best_items = current_items
        if i == n:
            return
        backtrack(i + 1, current_weight, current_value, current_items)
        backtrack(i + 1, current_weight + weights[i], current_value + values[i], current_items + [i])

    n = len(weights)
    max_value = 0
    best_items = []
    backtrack(0, 0, 0, [])
    return max_value, best_items


# 分支限界法求解0/1背包问题
def branch_bound_knapsack(weights, values, capacity):
    class Node:
        def __init__(self, level, weight, value, bound, items):
            self.level = level
            self.weight = weight
            self.value = value
            self.bound = bound
            self.items = items

    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
    best_items = []
    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, node.items)
        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, node.items + [node.level + 1])
        right.bound = bound(right)
        if right.weight <= capacity and right.value > max_value:
            max_value = right.value
            best_items = right.items
        if right.bound > max_value:
            Q.append(right)
    return max_value, best_items


# 测试程序
N = [4, 8, 16, 24]
times_brute_force = []
times_backtrack = []
times_branch_bound = []
for n in N:
    weights, values = generate_items(n)
    capacity = sum(weights) // 2

    start_time = time.time()
    brute_force_knapsack(weights, values, capacity)
    end_time = time.time()
    times_brute_force.append(end_time - start_time)

    start_time = time.time()
    backtrack_knapsack(weights, values, capacity)
    end_time = time.time()
    times_backtrack.append(end_time - start_time)

    start_time = time.time()
    branch_bound_knapsack(weights, values, capacity)
    end_time = time.time()
    times_branch_bound.append(end_time - start_time)

print(times_brute_force)
print(times_backtrack)
print(times_branch_bound)

在测试程序中，添加输出最优解的代码：

for n in N:
    weights, values = generate_items(n)
    capacity = sum(weights) // 2

    print("N =", n)
    print("Weights:", weights)
    print("Values:", values)
    print("Capacity:", capacity)

    max_value, best_items = brute_force_knapsack(weights, values, capacity)
    print("Brute Force:")
    print("Max Value:", max_value)
    print("Best Items:", best_items)

    max_value, best_items = backtrack_knapsack(weights, values, capacity)
    print("Backtrack:")
    print("Max Value:", max_value)
    print("Best Items:", best_items)

    max_value, best_items = branch_bound_knapsack(weights, values, capacity)
    print("Branch and Bound:")
    print("Max Value:", max_value)
    print("Best Items:", best_items)

    print()

这样就可以在运行程序时输出每种方法的最优解了。