三种方法解决0/1背包问题及Python代码实现

import random
import time


# 生成随机的物品重量和价值
def generate_items(n):
    weights = [random.randint(1, 10) for _ in range(n)]  # 生成n个随机物品的重量
    values = [random.randint(10, 50) for _ in range(n)]  # 生成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):  # 定义递归函数，i表示当前考虑的物品索引
        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)  # 不放入第i个物品
        backtrack(i + 1, current_weight + weights[i], current_value + values[i])  # 放入第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()