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

import random
import time
import matplotlib.pyplot as plt

def brute_force_knapsack(weights, values, capacity):
    n = len(weights)
    max_value = 0
    max_subset = []

    for i in range(2**n):
        subset = []
        total_weight = 0
        total_value = 0

        for j in range(n):
            if (i >> j) & 1:
                subset.append(j)
                total_weight += weights[j]
                total_value += values[j]

        if total_weight <= capacity and total_value > max_value:
            max_value = total_value
            max_subset = subset

    return max_value, max_subset

def generate_items(n):
    weights = []
    values = []
    for _ in range(n):
        weight = random.randint(1, 10)
        value = random.randint(10, 50)
        weights.append(weight)
        values.append(value)
    return weights, values

def calculate_time(n):
    weights, values = generate_items(n)
    capacity = sum(weights) // 2

    start_time = time.time()
    brute_force_knapsack(weights, values, capacity)
    end_time = time.time()

    return end_time - start_time

def plot_graph(n_values, time_values):
    plt.plot(n_values, time_values)
    plt.xlabel('物品数量N')
    plt.ylabel('运行时间 (秒)')
    plt.title('蛮力法求解0/1背包问题的时间复杂度')
    plt.show()

if __name__ == '__main__':
    n_values = []
    time_values = []

    for n in range(4, 33, 4):
        n_values.append(n)
        time_values.append(calculate_time(n))

    plot_graph(n_values, time_values)

代码说明：

1. brute_force_knapsack(weights, values, capacity): 该函数实现了蛮力法求解0/1背包问题。
2. generate_items(n): 该函数用于生成n个物品的随机重量和价值。
3. calculate_time(n): 该函数计算对于n个物品，使用蛮力法求解0/1背包问题所需的时间。
4. plot_graph(n_values, time_values): 该函数根据给定的物品数量和对应时间绘制图表。

使用方法：

将以上代码复制到PyCharm中运行，即可生成一个图表，横坐标为物品数量N，纵坐标为运行时间，展示蛮力法求解0/1背包问题的时间复杂度。