回溯法解决01背包问题c语言

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

#include <stdio.h>

#define MAX_N 100

int n, w[MAX_N], v[MAX_N], W; // 物品数量n，每个物品的重量w和价值v，背包容量W
int max_value = 0; // 最大价值

void dfs(int i, int weight, int value) {
    if (i == n) { // 所有物品已经处理完
        if (weight <= W && value > max_value) { // 更新最大价值
            max_value = value;
        }
        return;
    }

    dfs(i + 1, weight, value); // 不选第i个物品

    if (weight + w[i] <= W) { // 如果选第i个物品不超过背包容量
        dfs(i + 1, weight + w[i], value + v[i]); // 选第i个物品
    }
}

int main() {
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    dfs(0, 0, 0); // 从第0个物品开始搜索
    printf("%d\n", max_value); // 输出最大价值
    return 0;
}

该算法的时间复杂度为 $O(2^n)$，当物品数量较大时，运行速度较慢。因此，在实际应用中，我们通常使用动态规划算法来解决01背包问题。