0/1 背包问题算法比较：蛮力法、回溯法和分支限界法

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:
                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]
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

plt.plot(N, times_brute_force, label='Brute Force')
plt.plot(N, times_backtrack, label='Backtrack')
plt.plot(N, times_branch_bound, label='Branch and Bound')

# Fit a polynomial curve to the data points
curve_brute_force = np.polyfit(N, times_brute_force, 3)
curve_backtrack = np.polyfit(N, times_backtrack, 3)
curve_branch_bound = np.polyfit(N, times_branch_bound, 3)

# 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()

上述代码实现了求解0/1背包问题的三种算法：蛮力法、回溯法和分支限界法。下面是代码的逐行解释：

import random: 导入random模块，用于生成随机数。
import time: 导入time模块，用于计算算法的执行时间。
def generate_items(n): 定义一个函数，用于生成随机的物品重量和价值。函数接受一个参数n，表示物品的数量。函数内部使用random.randint函数生成n个随机的重量和价值，并将它们分别保存在weights和values列表中，最后返回这两个列表。
def brute_force_knapsack(weights, values, capacity): 定义一个函数，用蛮力法求解0/1背包问题。函数接受三个参数：weights表示物品的重量列表，values表示物品的价值列表，capacity表示背包的容量。函数内部使用两层循环遍历所有可能的物品组合，计算每个组合的总重量和总价值，并找到满足背包容量限制的最大总价值。最后返回最大总价值。
def backtrack_knapsack(weights, values, capacity): 定义一个函数，用回溯法求解0/1背包问题。函数接受三个参数：weights表示物品的重量列表，values表示物品的价值列表，capacity表示背包的容量。函数内部定义了一个嵌套函数backtrack，用于递归地搜索所有可能的物品组合。函数内部使用回溯法的思想，在每一步选择是否放入当前物品，计算当前组合的总重量和总价值，并更新最大总价值。最后返回最大总价值。
def branch_bound_knapsack(weights, values, capacity): 定义一个函数，用分支限界法求解0/1背包问题。函数接受三个参数：weights表示物品的重量列表，values表示物品的价值列表，capacity表示背包的容量。函数内部定义了一个内部类Node，用于表示搜索树的节点。函数内部定义了一个嵌套函数bound，用于计算节点的上界。函数内部使用分支限界法的思想，维护一个优先队列Q，初始时将根节点加入队列。然后从队列中取出节点进行扩展，计算节点的上界并进行剪枝。最后返回最大总价值。
N = [4, 8, 16]: 定义一个列表N，表示物品的数量。
times_brute_force = []: 定义一个空列表times_brute_force，用于保存蛮力法求解时间。
times_backtrack = []: 定义一个空列表times_backtrack，用于保存回溯法求解时间。
times_branch_bound = []: 定义一个空列表times_branch_bound，用于保存分支限界法求解时间。
for n in N:: 遍历列表N中的每个元素n，表示物品的数量。
weights, values = generate_items(n): 调用generate_items函数生成随机的物品重量和价值，将结果保存在weights和values变量中。
capacity = sum(weights) // 2: 计算背包的容量，为物品重量的和的一半。
start_time = time.time(): 记录当前时间，用于计算算法的执行时间。
brute_force_knapsack(weights, values, capacity): 调用蛮力法求解0/1背包问题。
end_time = time.time(): 记录当前时间，用于计算算法的执行时间。
times_brute_force.append(end_time - start_time): 将蛮力法求解时间添加到times_brute_force列表中。
start_time = time.time(): 记录当前时间，用于计算算法的执行时间。
backtrack_knapsack(weights, values, capacity): 调用回溯法求解0/1背包问题。
end_time = time.time(): 记录当前时间，用于计算算法的执行时间。
times_backtrack.append(end_time - start_time): 将回溯法求解时间添加到times_backtrack列表中。
start_time = time.time(): 记录当前时间，用于计算算法的执行时间。
branch_bound_knapsack(weights, values, capacity): 调用分支限界法求解0/1背包问题。
end_time = time.time(): 记录当前时间，用于计算算法的执行时间。
times_branch_bound.append(end_time - start_time): 将分支限界法求解时间添加到times_branch_bound列表中。
import matplotlib.pyplot as plt: 导入matplotlib.pyplot模块，用于绘制图表。
import numpy as np: 导入numpy模块，用于进行数值计算。
plt.plot(N, times_brute_force, label='Brute Force'): 绘制蛮力法求解时间的折线图。
plt.plot(N, times_backtrack, label='Backtrack'): 绘制回溯法求解时间的折线图。
plt.plot(N, times_branch_bound, label='Branch and Bound'): 绘制分支限界法求解时间的折线图。
curve_brute_force = np.polyfit(N, times_brute_force, 3): 使用np.polyfit函数对蛮力法求解时间进行多项式拟合，拟合的阶数为3，将拟合结果保存在curve_brute_force变量中。
curve_backtrack = np.polyfit(N, times_backtrack, 3): 使用np.polyfit函数对回溯法求解时间进行多项式拟合，拟合的阶数为3，将拟合结果保存在curve_backtrack变量中。
curve_branch_bound = np.polyfit(N, times_branch_bound, 3): 使用np.polyfit函数对分支限界法求解时间进行多项式拟合，拟合的阶数为3，将拟合结果保存在curve_branch_bound变量中。
smooth_N = np.linspace(min(N), max(N), 100): 使用np.linspace函数生成100个均匀分布的数值，作为平滑曲线的横坐标。
smooth_times_brute_force = np.polyval(curve_brute_force, smooth_N): 使用np.polyval函数根据多项式拟合结果计算平滑曲线的纵坐标。
smooth_times_backtrack = np.polyval(curve_backtrack, smooth_N): 使用np.polyval函数根据多项式拟合结果计算平滑曲线的纵坐标。
smooth_times_branch_bound = np.polyval(curve_branch_bound, smooth_N): 使用np.polyval函数根据多项式拟合结果计算平滑曲线的纵坐标。
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'): 设置x轴的标签为'N'。
plt.ylabel('Time (s)'): 设置y轴的标签为'Time (s)'。
plt.legend(): 显示图例。
plt.show(): 显示图表。