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

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

import random
import math

def simulated_annealing(values, weights, capacity, temperature=1000, cooling_rate=0.95, stopping_temperature=1e-8, num_iterations=1000):
    """
    使用模拟退火算法求解01背包问题

    :param values: 物品价值的列表
    :param weights: 物品重量的列表
    :param capacity: 背包容量
    :param temperature: 初始温度
    :param cooling_rate: 降温速率
    :param stopping_temperature: 终止温度
    :param num_iterations: 每个温度下的迭代次数
    :return: 最优解的价值和选择的物品列表
    """
    num_items = len(values)
    current_solution = [0] * num_items
    current_weight = 0
    current_value = 0
    best_solution = current_solution.copy()
    best_value = 0
    current_temperature = temperature

    while current_temperature > stopping_temperature:
        for i in range(num_iterations):
            # 随机选择一个物品
            item_index = random.randint(0, num_items - 1)

            # 生成新解
            new_solution = current_solution.copy()
            new_solution[item_index] = 1 - new_solution[item_index]
            new_weight = current_weight + (-1 if current_solution[item_index] else 1) * weights[item_index]
            new_value = current_value + (-1 if current_solution[item_index] else 1) * values[item_index]

            # 如果新解不符合约束条件，则不考虑它
            if new_weight > capacity:
                continue

            # 计算接受概率
            delta = new_value - current_value
            accept_prob = math.exp(delta / current_temperature)

            # 接受新解
            if delta > 0 or random.random() < accept_prob:
                current_solution = new_solution
                current_weight = new_weight
                current_value = new_value

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

        # 降温
        current_temperature *= cooling_rate

    return best_value, [i for i in range(num_items) if best_solution[i] == 1]

使用示例：

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
best_value, best_items = simulated_annealing(values, weights, capacity)
print("最优解的价值为：", best_value)
print("选择的物品为：", best_items)

输出：

最优解的价值为： 220
选择的物品为： [0, 1]