01背包问题回溯法c语言代码

以下是01背包问题的回溯法的c语言代码：

#include <stdio.h>

#define MAX_N 100    // 最大物品数
#define MAX_W 10000  // 最大背包容量

int N, W;           // 物品数，背包容量
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int max_v;          // 最大价值
int cur_w, cur_v;   // 当前重量和价值
int used[MAX_N];    // 当前物品是否被选中

void backtracking(int i) {
    if (i == N) { // 达到叶子节点，更新最大价值
        if (cur_v > max_v) {
            max_v = cur_v;
        }
        return;
    }
    if (cur_w + w[i] <= W) { // 如果当前物品可以放入背包
        cur_w += w[i];
        cur_v += v[i];
        used[i] = 1; // 标记当前物品被选中
        backtracking(i + 1); // 继续向下搜索
        cur_w -= w[i]; // 回溯，恢复现场
        cur_v -= v[i];
        used[i] = 0;
    }
    backtracking(i + 1); // 不选当前物品，继续向下搜索
}

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;
    backtracking(0);
    printf("%d\n", max_v);
    return 0;
}

该代码使用了全局变量来保存当前状态，包括当前重量和价值、是否选中物品等。回溯函数 `backtracking` 中，首先判断当前物品是否可以放入背包，如果可以，则选中该物品并继续向下搜索；如果不行，则直接跳过该物品，继续向下搜索。当搜索到叶子节点时，更新最大价值。在回溯时，要恢复现场，即将当前物品的选中状态、重量和价值还原。