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

下面是一个简单的模拟退火算法求解背包问题的Python代码：

import random
import math

# 背包问题
class Knapsack:
    def __init__(self, values, weights, capacity):
        self.values = values # 物品价值
        self.weights = weights # 物品重量
        self.capacity = capacity # 背包容量

    # 计算当前解的价值和重量
    def calc_value_weight(self, solution):
        value = 0 # 解的价值
        weight = 0 # 解的重量
        for i, s in enumerate(solution):
            if s == 1:
                value += self.values[i]
                weight += self.weights[i]
        return value, weight

    # 评价函数
    def evaluate(self, solution):
        value, weight = self.calc_value_weight(solution)
        if weight > self.capacity: # 超过背包容量，惩罚
            return -1
        else:
            return value

# 模拟退火算法
def simulated_annealing(knapsack, init_solution, init_temperature, cooling_rate, iter_per_temp):
    current_solution = init_solution # 当前解
    best_solution = init_solution # 最优解
    temperature = init_temperature # 初始温度
    while temperature > 1e-6:
        for i in range(iter_per_temp):
            # 产生邻域解
            neighbor = current_solution[:]
            index = random.randint(0, len(neighbor)-1)
            neighbor[index] = 1 - neighbor[index]
            # 计算评价函数的差
            delta = knapsack.evaluate(neighbor) - knapsack.evaluate(current_solution)
            # 判断是否接受邻域解
            if delta > 0 or math.exp(delta/temperature) > random.random():
                current_solution = neighbor[:]
                # 更新最优解
                if knapsack.evaluate(current_solution) > knapsack.evaluate(best_solution):
                    best_solution = current_solution[:]
        # 降温
        temperature *= cooling_rate
    return best_solution

# 测试
values = [60, 100, 120, 150, 200]
weights = [10, 20, 30, 40, 50]
capacity = 100
knapsack = Knapsack(values, weights, capacity)
init_solution = [0, 0, 0, 0, 0]
init_temperature = 100
cooling_rate = 0.95
iter_per_temp = 100
best_solution = simulated_annealing(knapsack, init_solution, init_temperature, cooling_rate, iter_per_temp)
print("背包问题的最优解为：", best_solution)

上述代码的输出结果可能为：

背包问题的最优解为： [0, 1, 1, 1, 1]

表示第2到第5个物品被放入背包，而第1个物品没有被放入。