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

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

import random
import math

# 背包容量
capacity = 50
# 物品重量
weights = [10, 20, 30, 40, 50]
# 物品价值
values = [50, 60, 140, 200, 240]
# 初始温度
init_temp = 100
# 温度下降速率
cooling_rate = 0.95
# 迭代次数
iterations = 1000

# 评估函数，计算当前解的价值
def eval_solution(solution):
    total_weight = 0
    total_value = 0
    for i in range(len(solution)):
        if solution[i] == 1:
            total_weight += weights[i]
            total_value += values[i]
    if total_weight > capacity:
        return 0
    else:
        return total_value

# 模拟退火算法
def simulated_annealing():
    # 初始化当前解和最优解
    current_solution = [random.randint(0, 1) for i in range(len(weights))]
    best_solution = current_solution
    # 初始化当前解的价值和最优解的价值
    current_value = eval_solution(current_solution)
    best_value = current_value
    # 初始化当前温度
    current_temp = init_temp
    # 迭代求解
    for i in range(iterations):
        # 生成新解
        new_solution = [random.randint(0, 1) for i in range(len(weights))]
        # 计算新解的价值
        new_value = eval_solution(new_solution)
        # 计算价值差
        delta = new_value - current_value
        # 判断是否接受新解
        if delta > 0:
            current_solution = new_solution
            current_value = new_value
            # 更新最优解
            if new_value > best_value:
                best_solution = new_solution
                best_value = new_value
        else:
            # 计算接受新解的概率
            p = math.exp(delta / current_temp)
            if random.random() < p:
                current_solution = new_solution
                current_value = new_value
        # 降温
        current_temp *= cooling_rate
    return best_solution, best_value

# 测试
best_solution, best_value = simulated_annealing()
print("最优解：", best_solution)
print("最优解的价值：", best_value)

代码说明：

- `eval_solution()` 函数用于评估当前解的价值。
- `simulated_annealing()` 函数实现模拟退火算法。
- `current_solution` 和 `best_solution` 分别表示当前解和最优解，它们都是由 0 和 1 组成的列表，其中 1 表示选择对应的物品，0 表示不选择。
- `current_value` 和 `best_value` 分别表示当前解的价值和最优解的价值。
- 在迭代求解过程中，每次生成一个新解，计算新解的价值，然后根据价值差和当前温度计算接受新解的概率，如果接受新解，则更新当前解和最优解。最后返回最优解和最优解的价值。
- 在测试中，调用 `simulated_annealing()` 函数求解01背包问题，并输出最优解和最优解的价值。

注意，以上代码只是一个简单的示例，实际应用中需要根据具体情况进行调整。