模拟退火算法求解背包问题python代码

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

import random
import math

# 背包问题求解函数
def knapsack(capacity, weights, values, max_iterations):
    # 初始化当前解和最佳解
    current_solution = [random.randint(0, 1) for i in range(len(weights))]
    best_solution = current_solution[:]
    # 计算当前解的价值和重量
    current_weight = sum([current_solution[i]*weights[i] for i in range(len(weights))])
    current_value = sum([current_solution[i]*values[i] for i in range(len(values))])
    # 初始化温度和降温速率
    temperature = 100
    cooling_rate = 0.03
    # 迭代求解
    for i in range(max_iterations):
        # 生成一个新解
        new_solution = current_solution[:]
        index = random.randint(0, len(weights)-1)
        new_solution[index] = 1 - new_solution[index] # 取反操作
        # 计算新解的价值和重量
        new_weight = sum([new_solution[i]*weights[i] for i in range(len(weights))])
        new_value = sum([new_solution[i]*values[i] for i in range(len(values))])
        # 计算能量差
        delta_e = new_value - current_value
        # 如果新解更优，则接受该解
        if new_weight <= capacity and delta_e > 0:
            current_solution = new_solution[:]
            current_weight = new_weight
            current_value = new_value
            # 更新最佳解
            if current_value > sum([best_solution[i]*values[i] for i in range(len(values))]):
                best_solution = current_solution[:]
        # 如果新解不优，则以一定概率接受该解
        else:
            probability = math.exp(delta_e/temperature)
            if random.random() < probability:
                current_solution = new_solution[:]
                current_weight = new_weight
                current_value = new_value
        # 降温
        temperature *= 1 - cooling_rate
    # 返回最佳解
    return best_solution

# 测试
capacity = 50
weights = [10, 20, 30, 40, 50]
values = [20, 30, 66, 40, 60]
max_iterations = 10000
best_solution = knapsack(capacity, weights, values, max_iterations)
best_weight = sum([best_solution[i]*weights[i] for i in range(len(weights))])
best_value = sum([best_solution[i]*values[i] for i in range(len(values))])
print("最佳解：", best_solution)
print("最佳重量：", best_weight)
print("最佳价值：", best_value)

这段代码中，我们通过模拟退火算法求解背包问题。首先，我们初始化当前解和最佳解为随机解，然后计算当前解的价值和重量。接着，我们初始化温度和降温速率，进行迭代求解。在每次迭代中，我们生成一个新解，计算新解的价值和重量，然后计算能量差。如果新解更优，则接受该解；否则，以一定概率接受该解。最后，我们返回最佳解。