Python实现蛮力法求解0/1背包问题及时间复杂度分析

import random
import time
import matplotlib.pyplot as plt

def brute_force_knapsack(weights, values, capacity):
    '''
    使用蛮力法求解0/1背包问题

    参数：
        weights: 物品重量列表
        values: 物品价值列表
        capacity: 背包容量

    返回值：
        max_value: 最大价值
        elapsed_time: 计算时间
    '''
    n = len(weights)
    max_value = 0
    start_time = time.time()
    
    # 枚举所有可能的物品组合
    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
    
    end_time = time.time()
    elapsed_time = end_time - start_time
    
    return max_value, elapsed_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

def plot_results(n_values, elapsed_times):
    '''绘制时间随问题规模变化的图像'''
    plt.plot(n_values, elapsed_times)
    plt.xlabel('物品数量N')
    plt.ylabel('计算时间 (秒)')
    plt.title('蛮力法求解0/1背包问题时间复杂度')
    plt.show()

if __name__ == '__main__':
    n_values = [4, 8, 16, 32, 64, 128]  # 问题规模
    elapsed_times = []
    
    for n in n_values:
        weights, values = generate_items(n)
        capacity = sum(weights) // 2
        max_value, elapsed_time = brute_force_knapsack(weights, values, capacity)
        elapsed_times.append(elapsed_time)
        
        print(f'物品数量 N={n}: 最大价值={max_value}, 计算时间={elapsed_time:.2f} 秒')
    
    plot_results(n_values, elapsed_times)