分支限界法解决01背包问题代码C语言

以下是使用分支限界法解决01背包问题的C语言代码：

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

#define N 5 // 物品数量
#define C 10 // 背包容量

// 物品结构体
typedef struct {
    int w; // 重量
    int v; // 价值
} item;

// 优先队列结构体
typedef struct {
    int level; // 当前层数（物品的序号）
    int profit; // 当前价值
    int weight; // 当前重量
} node;

// 比较函数
int cmp(const void* a, const void* b) {
    double r1 = ((item*)a)->v / (double)((item*)a)->w;
    double r2 = ((item*)b)->v / (double)((item*)b)->w;
    return r2 > r1 ? 1 : -1;
}

// 分支限界法求解01背包问题
int knapsack(item items[], int n, int capacity) {
    // 按单位重量价值从高到低排序
    qsort(items, n, sizeof(item), cmp);

    // 初始化优先队列
    node q[n + 1];
    int front = 0, rear = 0;
    q[rear++] = (node){-1, 0, 0}; // 初始节点

    // 迭代扩展节点
    int max_profit = 0;
    while (front != rear) {
        node u = q[front++];
        if (u.level == n - 1) continue; // 已经扩展到叶节点

        // 扩展左儿子节点（不装当前物品）
        node left = {
            u.level + 1, // 物品序号加1
            u.profit,
            u.weight
        };
        q[rear++] = left;

        // 扩展右儿子节点（装当前物品）
        node right = {
            u.level + 1, // 物品序号加1
            u.profit + items[u.level + 1].v,
            u.weight + items[u.level + 1].w
        };
        if (right.weight <= capacity && right.profit > max_profit) {
            max_profit = right.profit;
        }
        if (bound(right, items, n, capacity) > max_profit) {
            q[rear++] = right;
        }
    }

    return max_profit;
}

// 计算当前节点的上界
int bound(node u, item items[], int n, int capacity) {
    int j, k;
    int totweight;
    int bound;

    if (u.weight >= capacity) {
        return 0;
    }

    bound = u.profit;
    j = u.level + 1;
    totweight = u.weight;

    while ((j < n) && (totweight + items[j].w <= capacity)) {
        totweight += items[j].w;
        bound += items[j].v;
        j++;
    }

    k = j;
    if (k < n) {
        bound += (capacity - totweight) * items[k].v / (double)items[k].w;
    }

    return bound;
}

// 测试
int main() {
    item items[N] = {
        {2, 6},
        {2, 3},
        {6, 5},
        {5, 4},
        {4, 6}
    };
    int capacity = C;
    int max_profit = knapsack(items, N, capacity);
    printf("Max profit: %d\n", max_profit);
    return 0;
}

注意：此代码实现中使用了优先队列来辅助实现分支限界法。如果对优先队列不熟悉，可以先了解一下优先队列的相关知识。