import random import time

生成随机的物品重量和价值

def generate_items(n): weights = [random.randint(1, 10) for _ in range(n)] values = [random.randint(10, 50) for _ in range(n)] return weights, values

蛮力法求解0/1背包问题

def brute_force_knapsack(weights, values, capacity): n = len(weights) max_value = 0 for i in range(2 ** n): #遍历所有可能的物品组合 current_weight = 0 current_value = 0 for j in range(n): if (i >> j) & 1: #判断第j个物品是否在当前组合中 current_weight += weights[j] current_value += values[j] if current_weight <= capacity and current_value > max_value: max_value = current_value return max_value

回溯法求解0/1背包问题

def backtrack_knapsack(weights, values, capacity): def backtrack(i, current_weight, current_value): nonlocal max_value if current_weight > capacity: return if current_value > max_value: max_value = current_value if i == n: return backtrack(i + 1, current_weight, current_value) backtrack(i + 1, current_weight + weights[i], current_value + values[i])

n = len(weights)
max_value = 0
backtrack(0, 0, 0)
return max_value

分支限界法求解0/1背包问题

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

测试程序

N = [4, 8, 16, 20] 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)

import matplotlib.pyplot as plt import numpy as np

Fit a polynomial curve to the data points

curve_brute_force = np.polyfit(N, times_brute_force, 20) curve_backtrack = np.polyfit(N, times_backtrack, 20) curve_branch_bound = np.polyfit(N, times_branch_bound, 20)

Generate a smooth curve using the fitted polynomial coefficients

smooth_N = np.linspace(min(N), max(N), 100) smooth_times_brute_force = np.polyval(curve_brute_force, smooth_N) smooth_times_backtrack = np.polyval(curve_backtrack, smooth_N) smooth_times_branch_bound = np.polyval(curve_branch_bound, smooth_N)

plt.plot(smooth_N, smooth_times_brute_force, label='Brute Force (Curve)') plt.plot(smooth_N, smooth_times_backtrack, label='Backtrack (Curve)') plt.plot(smooth_N, smooth_times_branch_bound, label='Branch and Bound (Curve)')

plt.xlabel('N') plt.ylabel('Time (s)') plt.legend() plt.show() 逐行解释代码内容：1. 导入random和time模块。 2. 定义generate_items函数，用于生成随机的物品重量和价值。参数n表示物品数量，函数返回weights和values两个列表，分别表示物品的重量和价值。 3. 定义brute_force_knapsack函数，使用蛮力法求解0/1背包问题。参数weights和values分别表示物品的重量和价值，capacity表示背包的容量。函数返回最大价值。 4. 定义backtrack_knapsack函数，使用回溯法求解0/1背包问题。参数weights和values分别表示物品的重量和价值，capacity表示背包的容量。函数返回最大价值。 5. 定义branch_bound_knapsack函数，使用分支限界法求解0/1背包问题。参数weights和values分别表示物品的重量和价值，capacity表示背包的容量。函数返回最大价值。 6. 定义一个列表N，包含不同的物品数量。 7. 定义三个空列表times_brute_force、times_backtrack和times_branch_bound，用于存储不同物品数量下的求解时间。 8. 使用for循环遍历N列表中的每个物品数量n。 9. 调用generate_items函数生成随机的物品重量和价值。 10. 计算背包容量capacity，为物品重量之和的一半。 11. 记录开始时间。 12. 调用brute_force_knapsack函数求解0/1背包问题。 13. 记录结束时间，并计算求解时间，并将其添加到times_brute_force列表中。 14. 记录开始时间。 15. 调用backtrack_knapsack函数求解0/1背包问题。 16. 记录结束时间，并计算求解时间，并将其添加到times_backtrack列表中。 17. 记录开始时间。 18. 调用branch_bound_knapsack函数求解0/1背包问题。 19. 记录结束时间，并计算求解时间，并将其添加到times_branch_bound列表中。 20. 导入matplotlib.pyplot和numpy模块。 21. 使用np.polyfit函数对N和times_brute_force列表进行多项式拟合，得到拟合曲线的系数curve_brute_force。 22. 使用np.polyfit函数对N和times_backtrack列表进行多项式拟合，得到拟合曲线的系数curve_backtrack。 23. 使用np.polyfit函数对N和times_branch_bound列表进行多项式拟合，得到拟合曲线的系数curve_branch_bound。 24. 使用np.linspace函数生成100个均匀分布的数值，作为平滑曲线的横坐标。 25. 使用np.polyval函数根据拟合曲线的系数和平滑曲线的横坐标生成平滑曲线的纵坐标smooth_times_brute_force。 26. 使用np.polyval函数根据拟合曲线的系数和平滑曲线的横坐标生成平滑曲线的纵坐标smooth_times_backtrack。 27. 使用np.polyval函数根据拟合曲线的系数和平滑曲线的横坐标生成平滑曲线的纵坐标smooth_times_branch_bound。 28. 使用plt.plot函数绘制平滑曲线，分别表示蛮力法、回溯法和分支限界法的求解时间。 29. 使用plt.xlabel和plt.ylabel函数设置横纵坐标的标签。 30. 使用plt.legend函数显示图例。 31. 使用plt.show函数显示图形。