背包问题采用回溯与分支限界C语言代码

好的，下面是使用回溯与分支限界算法实现0-1背包问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int w; // 物品重量
    int v; // 物品价值
} Item;

int n, c; // 物品数量和背包容量
Item *items; // 物品数组
int maxValue; // 当前最大价值
int *selected; // 当前选择的物品

// 计算当前选择的物品总价值
int totalValue() {
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (selected[i]) {
            total += items[i].v;
        }
    }
    return total;
}

// 回溯函数
void backtrack(int i, int currentWeight, int currentValue) {
    if (i == n) { // 所有物品都已经选择完毕
        if (currentValue > maxValue) {
            maxValue = currentValue;
        }
        return;
    }

    // 不选择第i件物品
    selected[i] = 0;
    backtrack(i+1, currentWeight, currentValue);

    // 选择第i件物品
    if (currentWeight + items[i].w <= c) { // 背包还能容纳
        selected[i] = 1;
        backtrack(i+1, currentWeight+items[i].w, currentValue+items[i].v);
        selected[i] = 0;
    }
}

// 分支限界函数
void branchAndBound() {
    selected = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        selected[i] = 0; // 初始化选择数组
    }

    // 回溯搜索
    backtrack(0, 0, 0);

    // 输出结果
    printf("%d\n", maxValue);

    // 释放内存
    free(selected);
}

int main() {
    scanf("%d %d", &n, &c);

    // 定义物品数组
    items = (Item *)malloc(sizeof(Item) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].w, &items[i].v);
    }

    // 分支限界
    branchAndBound();

    // 释放内存
    free(items);

    return 0;
}

这里使用了回溯算法和分支限界算法相结合的方法来解决0-1背包问题。在回溯函数中，对于每一个物品，都有两种选择：放入背包中或者不放。如果放入，则需要检查背包容量是否足够，如果足够，则继续回溯搜索；如果不足，则剪枝返回。如果不放入，则直接进行回溯搜索。在搜索过程中，需要维护当前选择的物品和总价值，并对比已搜索到的最大价值来更新结果。在分支限界函数中，需要初始化选择数组，调用回溯函数进行搜索，并输出最终结果。