用c语言回溯法实现01背包问题

下面是用 C 语言实现 01 背包问题的回溯法算法：

#include <stdio.h>
#define MAX_N 100

int N;  // 物品数量
int W;  // 背包容量
int w[MAX_N];  // 物品的重量
int v[MAX_N];  // 物品的价值
int max_v;  // 最大价值
int cur_w;  // 当前背包中物品总重量
int cur_v;  // 当前背包中物品总价值

// 回溯函数
void backtrack(int i) {
    if (i == N) {  // 达到叶子节点
        if (cur_v > max_v) {
            max_v = cur_v;  // 更新最大价值
        }
    } else {
        // 不选第 i 个物品
        backtrack(i+1);

        // 选第 i 个物品
        if (cur_w + w[i] <= W) {  // 能放下第 i 个物品
            cur_w += w[i];
            cur_v += v[i];
            backtrack(i+1);
            cur_w -= w[i];
            cur_v -= v[i];
        }
    }
}

int main() {
    scanf("%d %d", &N, &W);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    max_v = 0;
    cur_w = 0;
    cur_v = 0;
    backtrack(0);

    printf("最大价值 = %d\n", max_v);

    return 0;
}

该算法的时间复杂度为 $O(2^N)$，因为每个物品都有选或不选两种可能，总共有 $2^N$ 种可能。