模拟退火01背包问题python

以下是使用模拟退火算法求解01背包问题的Python代码：

import random
import math

def simulated_annealing(weights, values, capacity, initial_temperature, cooling_rate, iterations):
    current_solution = [0] * len(weights)
    best_solution = current_solution.copy()
    current_value = 0
    best_value = 0

    current_temperature = initial_temperature

    for _ in range(iterations):
        # 随机选择一个物品
        index = random.randint(0, len(weights) - 1)

        # 切换物品的状态
        current_solution[index] = 1 - current_solution[index]

        # 计算当前解的价值
        current_value = sum([values[i] * current_solution[i] for i in range(len(weights))])

        # 如果当前解超过了背包容量，则撤销切换
        if sum([weights[i] * current_solution[i] for i in range(len(weights))]) > capacity:
            current_solution[index] = 1 - current_solution[index]
            current_value = best_value

        # 更新最优解
        if current_value > best_value:
            best_solution = current_solution.copy()
            best_value = current_value

        # 计算接受概率
        acceptance_probability = math.exp((current_value - best_value) / current_temperature)

        # 根据接受概率决定是否接受新解
        if random.random() > acceptance_probability:
            current_solution[index] = 1 - current_solution[index]
            current_value = best_value

        # 降低温度
        current_temperature *= cooling_rate

    return best_solution, best_value

weights = [2, 3, 5, 1, 4]
values = [2, 5, 8, 3, 6]
capacity = 10
initial_temperature = 100
cooling_rate = 0.95
iterations = 1000

best_solution, best_value = simulated_annealing(weights, values, capacity, initial_temperature, cooling_rate, iterations)

print("Best solution:", best_solution)
print("Best value:", best_value)