01背包问题回溯法C代码

01背包问题是动态规划中常见的一个问题，用于在给定物品重量和价值的情况下，选择能放入背包的最大价值。回溯法也可以用来解决这个问题，但相对于动态规划来说，它的时间复杂度较高。以下是一个简单的01背包问题回溯法的C语言实现：

#include <stdio.h>
#include <limits.h>

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

// 回溯函数
int knapsackRecursion(int capacity, Item items[], int n, int currWeight, int totalValue) {
    if (currWeight == 0 || n == 0 || capacity == 0) {
        return totalValue;
    }
    
    // 如果当前物品能装入背包
    int option1 = knapsackRecursion(capacity - items[n-1].weight, items, n, currWeight - items[n-1].weight, totalValue + items[n-1].value);
    
    // 如果不装入当前物品
    int option2 = knapsackRecursion(capacity, items, n-1, currWeight, totalValue);

    // 选择最大值
    return option1 > option2 ? option1 : option2;
}

int main() {
    int capacity, numItems;
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);
    printf("Enter the number of items: ");
    scanf("%d", &numItems);

    Item items[numItems];
    for (int i = 0; i < numItems; i++) {
        printf("Enter weight and value for item %d: ", i+1);
        scanf("%d%d", &items[i].weight, &items[i].value);
    }

    int maxValue = knapsackRecursion(capacity, items, numItems, capacity, 0);
    printf("The maximum value that can be obtained is: %d\n", maxValue);

    return 0;
}