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

模拟退火算法是一种全局优化搜索算法，常用于解决复杂的组合优化问题，比如0-1背包问题。以下是使用C++编写的一个简化的模拟退火求解背包问题的例子：

#include <iostream>
#include <vector>
#include <random>
using namespace std;

// 背包状态表示，包含物品价值和重量
struct Item {
    int value;
    int weight;
};

// 定义背包类
class KnapsackProblem {
private:
    vector<Item> items;
    int capacity;
    int totalValue(int state) {
        int sum = 0;
        for (int i = 0; i < state.size(); ++i) {
            if (state[i] == 1) {
                sum += items[i].value;
            }
        }
        return sum;
    }

public:
    // 构造函数，传入物品列表和背包容量
    KnapsackProblem(vector<Item>& _items, int _capacity) : items(_items), capacity(_capacity) {}

    // 模拟退火搜索函数
    bool simulatedAnnealing() {
        int currentSol = getOptimalSolution();
        double T = 10000; // 初始温度
        double alpha = 0.95; // 冷却因子
        while (T > 1e-6 && totalValue(currentSol) != capacity) {
            vector<int> newSol = currentSol;
            random_shuffle(newSol.begin(), newSol.end()); // 随机打乱当前解
            int newTotalValue = totalValue(newSol);
            double delta = newTotalValue - totalValue(currentSol);

            // 接受新解的概率计算
            double p = exp(-delta / T);
            if (rand() / static_cast<double>(RAND_MAX) < p || delta >= 0) {
                currentSol = newSol;
            }
            T *= alpha; // 温度随迭代下降
        }
        return totalValue(currentSol) == capacity; // 如果找到满载解决方案，返回true
    }

    // 获取最优解
    vector<int> getOptimalSolution() {
        vector<int> solution(items.size(), 0);
        sort(items.rbegin(), items.rend(), [](const Item& a, const Item& b) { return a.value / a.weight > b.value / b.weight; });
        for (Item item : items) {
            if (totalWeight(solution) + item.weight <= capacity) {
                solution.back() = 1;
            } else {
                break;
            }
        }
        return solution;
    }

    int totalWeight(const vector<int>& sol) {
        int sum = 0;
        for (int w : sol) {
            sum += w ? items[w - 1].weight : 0;
        }
        return sum;
    }
};

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int capacity = 50;
    KnapsackProblem kp(items, capacity);
    cout << "Is optimal solution found by simulated annealing? " << (kp.simulatedAnnealing() ? "Yes" : "No") << endl;
    return 0;
}

这个代码首先定义了一个`KnapsackProblem`类，包含了物品列表、背包容量以及计算总价值的方法。`simulatedAnnealing`函数实现了模拟退火算法，通过不断尝试随机生成的新解并接受概率较高的改进，直到达到满足条件的解。

注意，这只是一个简化版本，实际应用中可能会更复杂，并考虑更多的优化策略和细节。