0-1背包问题回溯法，C语言完整代码

0-1背包问题是动态规划问题的一种经典形式，但在处理一些特定场景下可以用回溯法解决。回溯算法通常用于组合优化问题，比如选择哪些物品放入背包以达到最大价值。以下是使用C语言的一个简单回溯法解0-1背包问题的示例：

#include <stdio.h>
#define W 10 // 背包容量
#define N 5 // 物品数量

// 定义物品结构体
typedef struct {
    int weight;  // 物品重量
    int value;   // 物品价值
} Item;

// 回溯函数
bool backtracking(Item items[], int n, int capacity, int total_value, int curr_weight) {
    if (curr_weight == capacity && total_value == -1) { // 满载且找到最大价值，成功
        printf("Max value with given capacity: %d\n", total_value);
        return true;
    }
    for (int i = 0; i < n; ++i) {
        if (curr_weight + items[i].weight <= capacity) { // 空间足够放下物品
            // 尝试包含当前物品
            bool include_item = backtracking(items, n, capacity, total_value + items[i].value, curr_weight + items[i].weight);
            if (include_item) return true; // 如果可以得到更大值，就返回true
        }
    }
    return false; // 如果无法增加总价值，返回false，回溯
}

int main() {
    Item items[] = {{60, 100}, {100, 200}, {120, 300}, {80, 180}, {150, 400}}; // 物品数组
    int n = sizeof(items) / sizeof(items[0]);
    
    // 初始化总价值和当前重量为负数
    int total_value = -1, curr_weight = 0;

    // 开始回溯搜索
    if (!backtracking(items, n, W, total_value, curr_weight)) {
        printf("No solution found.\n");
    }

    return 0;
}

这个代码首先定义了一个物品结构体，然后定义了`backtracking`函数来进行回溯。在主函数中，我们提供了一组物品和背包容量，并开始回溯寻找最大的总价值。