暴力法求解背包问题绘图时遇维度不匹配ValueError报错求助

报错原因 #

你的代码中绘图逻辑被错误缩进在for循环内部。第一次循环执行时，running_times仅收集到1条运行时间数据（长度为1），但input_sizes的长度是5，此时调用plt.plot(input_sizes, running_times)会因x、y数组维度不匹配触发报错。

解决方法 #

将所有绘图相关代码（从plt.plot()到plt.show()）移至for循环外部，确保等running_times收集完所有5组输入规模对应的运行时间后，再执行绘图操作。

修正后的完整代码 #

import time
import random
import matplotlib.pyplot as plt

def brute_force(values, weights, capacity):
    num_items = len(values)
    max_value = 0
    subset = []
    
    for i in range(2**num_items):
        current_value = 0
        current_weight = 0
        current_subset = []
        
        for j in range(num_items):
            if(i & (1 << j)) != 0:
                current_value += values[j]
                current_weight += weights[j]
                current_subset.append(j)
                
        if current_weight <= capacity and current_value > max_value:
            max_value = current_value
            subset = current_subset
            
    return max_value, subset

input_sizes = [10, 20, 30, 40, 50]
running_times = []
for size in input_sizes:
    values = [random.randint(1,100) for _ in range(size)]
    weights = [random.randint(1, 100) for _ in range(size)]
    capacity = sum(weights) // 2

    start_time = time.time()
    max_value, subset = brute_force(values, weights, capacity)
    end_time = time.time()
    running_time = end_time - start_time
    running_times.append(running_time)

    print(f"Input size: {size}")
    print(f"Chosen subset: {subset}")
    print(f"Chosen weight: {sum(weights[i] for i in subset)}")
    print(f"Running time: {running_time: .6f} seconds")

# 绘图代码移至循环外部
plt.plot(input_sizes, running_times, marker = 'o')
plt.xlabel('Input size')
plt.ylabel('Running time (s)')
plt.title('Brute force Knapsack')
plt.show()  

内容的提问来源于stack exchange，提问作者Cheeto Chief