01背包问题回溯法c语言

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

#include <stdio.h>

#define MAX_N 100     // 背包最大容量
#define MAX_M 100     // 物品最多个数

int weight[MAX_M];    // 物品重量数组
int value[MAX_M];     // 物品价值数组
int max_value;        // 最大价值
int n, m;             // n=物品个数，m=背包容量
int x[MAX_M];         // 当前解

// 计算当前解的价值
int calcCurrentValue() {
    int sum_w = 0, sum_v = 0;
    for (int i = 0; i < n; i++) {
        if (x[i]) {  // 第i个物品被选中
            sum_w += weight[i];
            sum_v += value[i];
        }
    }
    if (sum_w <= m && sum_v > max_value) {
        max_value = sum_v;
    }
    return sum_v;
}

// 递归求解01背包问题
void backtrack(int t) {
    if (t >= n) {
        calcCurrentValue();
        return;
    }
    // 遍历第t个物品选或不选
    for (int i = 0; i <= 1; i++) {
        x[t] = i;  // 选择或不选
        if (calcCurrentValue() + (n - t - 1) * value[t] > max_value) {
            backtrack(t + 1);  // 继续探索
        }
        x[t] = 0;  // 回溯
    }
}

int main() {
    // 读入物品信息和背包容量
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    // 求解01背包问题
    max_value = 0;
    backtrack(0);
    printf("The maximum value is %d.\n", max_value);
    return 0;
}

该算法的时间复杂度为 O(2^n)，因为对于每个物品，都有选或不选两种情况，共有 n 个物品，所以总共有 2^n 种情况需要考虑。在实际应用中，背包问题的数据规模往往比较大，回溯法的时间复杂度很高，因此需要使用其他高效的算法来解决背包问题。