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

以下是用C语言实现模拟退火算法解决01背包问题的代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define MAX_WEIGHT 100  // 背包最大承重
#define MAX_ITEM 20     // 物品数量

// 物品结构体
typedef struct {
    int weight;         // 重量
    int value;          // 价值
} Item;

// 生成随机物品
void generate_items(Item *items, int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        items[i].weight = rand() % 30 + 1;
        items[i].value = rand() % 50 + 1;
    }
}

// 计算当前解的总价值
int calc_value(int *solution, Item *items, int n) {
    int value = 0;
    for (int i = 0; i < n; i++) {
        if (solution[i]) {
            value += items[i].value;
        }
    }
    return value;
}

// 计算当前解的总重量
int calc_weight(int *solution, Item *items, int n) {
    int weight = 0;
    for (int i = 0; i < n; i++) {
        if (solution[i]) {
            weight += items[i].weight;
        }
    }
    return weight;
}

// 随机交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 模拟退火算法
void simulated_annealing(Item *items, int n, int *solution) {
    int current_value, current_weight, new_value, new_weight, best_value, best_weight;
    double temperature = 100.0, cooling_rate = 0.99;
    int iterations = 1000, inner_loop = 100;

    // 初始化当前解、最优解
    for (int i = 0; i < n; i++) {
        solution[i] = rand() % 2;
    }
    current_value = calc_value(solution, items, n);
    current_weight = calc_weight(solution, items, n);
    best_value = current_value;
    best_weight = current_weight;

    // 退火过程
    while (temperature > 1.0) {
        for (int i = 0; i < iterations; i++) {
            for (int j = 0; j < inner_loop; j++) {
                // 随机选取一个物品，进行翻转
                int index = rand() % n;
                int new_solution[MAX_ITEM];
                for (int k = 0; k < n; k++) {
                    new_solution[k] = solution[k];
                }
                new_solution[index] = 1 - new_solution[index];

                // 计算新解的价值、重量
                new_value = calc_value(new_solution, items, n);
                new_weight = calc_weight(new_solution, items, n);

                // 如果新解更优或者符合Metropolis准则，则接受新解
                if (new_weight <= MAX_WEIGHT && (new_value > current_value || exp((new_value - current_value) / temperature) > (double)rand() / RAND_MAX)) {
                    for (int k = 0; k < n; k++) {
                        solution[k] = new_solution[k];
                    }
                    current_value = new_value;
                    current_weight = new_weight;
                }

                // 更新最优解
                if (current_value > best_value) {
                    best_value = current_value;
                    best_weight = current_weight;
                }
            }
        }
        temperature *= cooling_rate;
    }

    // 输出结果
    printf("最大价值为：%d，总重量为：%d\n", best_value, best_weight);
    printf("选中的物品为：");
    for (int i = 0; i < n; i++) {
        if (solution[i]) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
}

// 主函数
int main() {
    Item items[MAX_ITEM];
    int solution[MAX_ITEM];
    generate_items(items, MAX_ITEM);
    simulated_annealing(items, MAX_ITEM, solution);
    return 0;
}

代码中使用了随机翻转、Metropolis准则和温度衰减等模拟退火算法的基本思想，通过不断迭代，寻找更优的解。