采用回溯法求解0/1背包问题C语言实现

下面是一个使用回溯法求解0/1背包问题的C语言实现：

#include <stdio.h>

#define MAX_N 1000

int n, w[MAX_N], v[MAX_N], W;
int max_v = 0, cur_v = 0, cur_w = 0;

void dfs(int i) {
    if (i == n) {
        if (cur_v > max_v) {
            max_v = cur_v;
        }
        return;
    }

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

    // 选第i个物品
    if (cur_w + w[i] <= W) {
        cur_w += w[i];
        cur_v += v[i];
        dfs(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]);
    }

    dfs(0);

    printf("%d\n", max_v);

    return 0;
}

其中，`dfs(i)`表示在处理前i个物品的情况下，已经选取的物品的总价值为`cur_v`，总重量为`cur_w`，并且还需要从第i个物品开始考虑。在`dfs`函数中，首先考虑不选第i个物品的情况，然后考虑选第i个物品的情况。如果选取了第i个物品，就需要将`cur_v`和`cur_w`分别加上该物品的价值和重量，并继续考虑下一个物品。如果不选取第i个物品，则直接考虑下一个物品。最终，当考虑完所有物品时，如果当前选取的物品总价值大于已知的最大值`max_v`，则更新`max_v`为当前值。

该算法的时间复杂度为$O(2^n)$，因为对于每一个物品，它有被选取和不被选取两种可能，总共有$2^n$种情况。