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:               #判断第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]
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, 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()

代码解释：

import random
import time

导入所需的模块，random模块用于生成随机数，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

定义一个函数generate_items，用于生成随机的物品重量和价值。函数接受一个参数n，表示生成物品的数量。函数内部使用列表推导式生成n个随机的物品重量和价值，并返回这两个列表。

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

定义一个函数brute_force_knapsack，用于使用蛮力法求解0/1背包问题。函数接受三个参数，weights表示物品重量列表，values表示物品价值列表，capacity表示背包容量。函数内部使用两层循环遍历所有可能的物品组合，计算每种组合的重量和价值，并更新最大价值。最后返回最大价值。

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

定义一个函数backtrack_knapsack，用于使用回溯法求解0/1背包问题。函数接受三个参数，weights表示物品重量列表，values表示物品价值列表，capacity表示背包容量。函数内部定义了一个嵌套函数backtrack，用于递归地搜索所有可能的物品组合。在每一步递归中，判断当前组合的重量是否超过背包容量，如果超过则返回，否则判断当前价值是否大于最大价值，如果大于则更新最大价值。最后调用backtrack函数开始搜索，并返回最大价值。

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

定义一个函数branch_bound_knapsack，用于使用分支限界法求解0/1背包问题。函数接受三个参数，weights表示物品重量列表，values表示物品价值列表，capacity表示背包容量。函数内部定义了一个内部类Node，用于表示搜索树的节点。函数内部还定义了一个内部函数bound，用于计算一个节点的上界。函数内部首先创建一个空列表Q，用于存储待扩展的节点。然后创建一个根节点，并将其加入Q中。接下来进入一个循环，每次从Q中取出一个节点进行扩展。如果节点的层次等于n-1（即到达叶子节点），则跳过该节点。否则，创建左子节点和右子节点，并计算它们的上界。如果左子节点的上界大于最大价值，则将左子节点加入Q。如果右子节点的重量不超过背包容量并且价值大于最大价值，则更新最大价值。如果右子节点的上界大于最大价值，则将右子节点加入Q。最后返回最大价值。

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)

定义一个列表N，表示要测试的物品数量。然后创建三个空列表times_brute_force、times_backtrack和times_branch_bound，用于存储每种算法的运行时间。接下来使用for循环遍历N列表，每次迭代中生成随机的物品重量和价值，并计算背包容量。然后使用time模块的time函数记录开始时间，调用相应的求解函数，并记录结束时间。将运行时间差添加到相应的列表中。

import matplotlib.pyplot as plt
import numpy as np

导入matplotlib.pyplot模块用于绘图，numpy模块用于进行多项式拟合。

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)

使用numpy的polyfit函数进行多项式拟合，拟合的阶数为3。分别对times_brute_force、times_backtrack和times_branch_bound与N进行拟合，得到拟合曲线的系数。

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)

使用numpy的linspace函数生成100个均匀分布的数值，用于绘制平滑曲线。然后使用numpy的polyval函数根据拟合曲线的系数计算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()

使用matplotlib.pyplot的plot函数绘制平滑曲线，分别绘制蛮力法、回溯法和分支限界法的运行时间曲线。然后使用xlabel函数和ylabel函数设置x轴和y轴的标签，使用legend函数显示图例，最后使用show函数显示图形。