用模拟退火算法实现01背包问题的代码

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

import random
import math

def simulated_annealing(values, weights, max_weight, temperature=1000, cooling_rate=0.99, stopping_temperature=1e-8):
    # 初始化
    current_state = [random.randint(0, 1) for _ in range(len(values))]
    best_state = current_state
    current_fitness = evaluate(current_state, values, weights, max_weight)
    best_fitness = current_fitness

    # 迭代搜索
    while temperature > stopping_temperature:
        # 生成新状态
        new_state = generate_neighbor(current_state)
        new_fitness = evaluate(new_state, values, weights, max_weight)

        # 判断是否接受新状态
        delta_fitness = new_fitness - current_fitness
        if delta_fitness > 0 or math.exp(delta_fitness / temperature) > random.uniform(0, 1):
            current_state = new_state
            current_fitness = new_fitness

        # 更新最优解
        if current_fitness > best_fitness:
            best_state = current_state
            best_fitness = current_fitness

        # 降温
        temperature *= cooling_rate

    return best_state, best_fitness

def generate_neighbor(state):
    # 随机选择一个物品翻转其状态
    new_state = state[:]
    index = random.randint(0, len(state) - 1)
    new_state[index] = 1 - new_state[index]
    return new_state

def evaluate(state, values, weights, max_weight):
    # 计算状态的价值和重量
    total_value = sum([v * s for v, s in zip(values, state)])
    total_weight = sum([w * s for w, s in zip(weights, state)])

    # 超出背包容量则价值为负无穷
    if total_weight > max_weight:
        return -math.inf

    return total_value

# 示例
values = [10, 8, 4, 5, 3, 7]
weights = [4, 5, 12, 9, 1, 13]
max_weight = 30

best_state, best_fitness = simulated_annealing(values, weights, max_weight)
print("最优解：", best_state)
print("最优值：", best_fitness)

其中，`simulated_annealing` 函数是模拟退火算法的主函数，`generate_neighbor` 函数用于生成邻居状态，`evaluate` 函数用于评估状态的价值和重量。在示例中，我们使用了一个包含6个物品的01背包问题，背包最大容量为30。运行结果可能会因为随机数的不同而有所不同。