使用C语言写回溯算法解决背包问题

下面是使用C语言实现回溯算法解决背包问题的示例代码：

#include <stdio.h>

#define MAX_N 100

int n;              // 物品数量
int w[MAX_N];       // 物品重量
int v[MAX_N];       // 物品价值
int capacity;       // 背包容量
int max_value = 0;  // 最大价值

void backtrack(int i, int total_weight, int total_value) {
    if (total_weight > capacity) {
        return;
    }
    if (total_value + (capacity - total_weight) * v[i] <= max_value) {
        return;
    }
    if (i == n) {
        max_value = total_value;
        return;
    }
    // 选择当前物品
    backtrack(i + 1, total_weight + w[i], total_value + v[i]);
    // 不选择当前物品
    backtrack(i + 1, total_weight, total_value);
}

int main() {
    // 读入数据
    scanf("%d %d", &n, &capacity);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    // 回溯搜索
    backtrack(0, 0, 0);
    // 输出结果
    printf("%d\n", max_value);
    return 0;
}

以上代码中，backtrack 函数的参数分别为当前物品的索引 i、当前已选物品的总重量 total_weight 和总价值 total_value。在函数中，我们首先判断当前已选物品的总重量是否超过了背包容量，如果超过了，则直接返回；然后判断当前已选物品的总价值加上剩余物品的最大价值是否小于等于 max_value，如果是，则也直接返回；如果当前已经选择了所有物品，则更新 max_value 并返回；否则，对于当前物品，分别尝试选择和不选择两种情况，分别调用 backtrack 函数进行递归搜索；在递归搜索结束后，需要撤销当前物品的选择，以便进行下一轮搜索。最终，我们得到的 max_value 即为最大价值。