Python实现三种方法解决0/1背包问题及时间复杂度比较

import random
import time
import matplotlib.pyplot as plt
import numpy as np


# 生成随机的物品重量和价值
def generate_items(n):
    # 生成n个随机的物品重量，重量范围为1到10
    weights = [random.randint(1, 10) for _ in range(n)]
    # 生成n个随机的物品价值，价值范围为10到50
    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):
            # 判断第j个物品是否在当前组合中
            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):
        # 如果当前节点的重量已经超过背包容量，则返回0
        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()
    # 蛮力法求解0/1背包问题
    brute_force_knapsack(weights, values, capacity)
    # 记录结束时间
    end_time = time.time()
    # 记录运行时间
    times_brute_force.append(end_time - start_time)

    # 记录开始时间
    start_time = time.time()
    # 回溯法求解0/1背包问题
    backtrack_knapsack(weights, values, capacity)
    # 记录结束时间
    end_time = time.time()
    # 记录运行时间
    times_backtrack.append(end_time - start_time)

    # 记录开始时间
    start_time = time.time()
    # 分支限界法求解0/1背包问题
    branch_bound_knapsack(weights, values, capacity)
    # 记录结束时间
    end_time = time.time()
    # 记录运行时间
    times_branch_bound.append(end_time - start_time)

# 蛮力法运行时间的多项式拟合曲线
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)

# 在最小值和最大值之间生成100个均匀分布的点
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)')

# x轴标签
plt.xlabel('N')
# y轴标签
plt.ylabel('Time (s)')
# 显示图例
plt.legend()
# 显示图像
plt.show()