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

回溯法是一种用于解决优化问题的算法，比如01背包问题，其中物品有固定的价值和体积，目标是在不超过背包容量的情况下选择物品以获得最大价值。以下是用C语言实现的简单版回溯法解01背包问题的代码示例：

#include <stdio.h>

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

// 求解函数
int knapsack(int W, Item items[], int n) {
    if (n == 0 || W == 0)
        return 0;
    if (items[n-1].weight <= W)
        return max(items[n-1].value + knapsack(W - items[n-1].weight, items, n-1),
                   knapsack(W, items, n-1));
    else
        return knapsack(W, items, n-1);
}

// 辅助函数，返回两个整数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

// 示例
int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50; // 背包容量
    int n = sizeof(items) / sizeof(items[0]); // 物品数量
    printf("最大价值：%d\n", knapsack(W, items, n));
    return 0;
}

这个代码首先定义了一个物品结构体，然后定义了`knapsack`函数来进行回溯搜索。在主函数里，我们创建了一个包含物品信息的数组，并指定背包的容量，最后计算并输出最大价值。