01背包回溯法c语言

以下是使用回溯法解决01背包问题的C语言代码示例：

#include <stdio.h>

#define MAX_N 100 // 最大物品数量
#define MAX_WEIGHT 1000 // 背包的最大承重

int weight[MAX_N]; // 物品的重量数组
int value[MAX_N]; // 物品的价值数组
int max_value; // 最大总价值
int best_choice[MAX_N]; // 最佳选择情况数组
int current_weight; // 当前背包内物品的总重量
int current_value; // 当前背包内物品的总价值

void backtrack(int n, int index) {
    if (index == n) { // 已经遍历完所有物品
        if (current_value > max_value) { // 更新最大总价值和最佳选择情况
            max_value = current_value;
            for (int i = 0; i < n; i++) {
                best_choice[i] = (current_weight >> i) & 1; // 1表示选择该物品，0表示不选择
            }
        }
        return;
    }
    
    if (current_weight + weight[index] <= MAX_WEIGHT) { // 选择当前物品
        current_weight += weight[index];
        current_value += value[index];
        backtrack(n, index + 1);
        current_weight -= weight[index];
        current_value -= value[index];
    }
    
    backtrack(n, index + 1); // 不选择当前物品
}

int main() {
    int n; // 物品数量
    printf("请输入物品数量：");
    scanf("%d", &n);
    
    printf("请依次输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    
    max_value = 0;
    current_weight = 0;
    current_value = 0;
    backtrack(n, 0);
    
    printf("最大总价值为：%d\n", max_value);
    printf("最佳选择情况为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", best_choice[i]);
    }
    printf("\n");
    
    return 0;
}