利用优先队列式分支限界法解决0-1背包问题c语言完整代码

以下是使用优先队列式分支限界法解决0-1背包问题的C语言完整代码：

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

#define MAX_N 100 // 物品数量的最大值
#define MAX_W 1000 // 背包容量的最大值

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

typedef struct {
    int level; // 节点所在的层数
    int profit; // 当前已选择物品的总价值
    int weight; // 当前已选择物品的总重量
    float bound; // 当前节点的价值上界
} Node;

// 用于比较两个Item结构体的p值
int cmp(const void* a, const void* b) {
    Item* i1 = (Item*)a;
    Item* i2 = (Item*)b;
    return (i2->p - i1->p) > 0 ? 1 : -1;
}

// 计算一个节点的价值上界
float bound(Node u, int n, Item* items, int w) {
    if (u.weight >= w) {
        return 0;
    }
    float profit_bound = u.profit;
    int j = u.level + 1;
    int totweight = u.weight;
    while ((j < n) && (totweight + items[j].w <= w)) {
        totweight += items[j].w;
        profit_bound += items[j].v;
        j++;
    }
    if (j < n) {
        profit_bound += (w - totweight) * items[j].p;
    }
    return profit_bound;
}

// 用于比较两个Node结构体的bound值
int cmp_node(const void* a, const void* b) {
    Node* n1 = (Node*)a;
    Node* n2 = (Node*)b;
    return (n2->bound - n1->bound) > 0 ? 1 : -1;
}

// 优先队列式分支限界法求解0-1背包问题
int solve_knapsack(int n, Item* items, int w) {
    // 按单位价值从大到小排序
    qsort(items, n, sizeof(Item), cmp);
    // 初始化队列
    Node* Q = (Node*)malloc(sizeof(Node) * MAX_N * 2);
    int head = 0, tail = 0;
    Node u, v;
    u.level = -1;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(u, n, items, w);
    Q[tail++] = u;
    int maxprofit = 0;
    while (head < tail) {
        // 取出队首节点
        u = Q[head++];
        if (u.bound > maxprofit) {
            // 生成左儿子节点，即不选当前物品
            v.level = u.level + 1;
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(v, n, items, w);
            if (v.bound > maxprofit) {
                Q[tail++] = v;
            }
            // 生成右儿子节点，即选择当前物品
            v.weight = u.weight + items[v.level].w;
            v.profit = u.profit + items[v.level].v;
            v.bound = bound(v, n, items, w);
            if ((v.weight <= w) && (v.profit > maxprofit)) {
                maxprofit = v.profit;
            }
            if (v.bound > maxprofit) {
                Q[tail++] = v;
            }
        }
    }
    free(Q);
    return maxprofit;
}

int main() {
    int n, w;
    scanf("%d %d", &n, &w);
    Item items[MAX_N];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].v, &items[i].w);
        items[i].p = (float)items[i].v / items[i].w;
    }
    int maxprofit = solve_knapsack(n, items, w);
    printf("%d\n", maxprofit);
    return 0;
}

在程序中，`Item`结构体表示一个物品，包含其价值、重量和单位价值；`Node`结构体表示搜索树中的一个节点，包含其所在层数、当前已选择物品的总价值、总重量和价值上界。`cmp`函数和`cmp_node`函数分别用于比较两个`Item`结构体和两个`Node`结构体的大小。`bound`函数用于计算一个节点的价值上界。`solve_knapsack`函数是主要的求解函数，其中使用优先队列来实现分支限界的过程。

在`main`函数中，首先输入物品数量和背包容量，然后输入每个物品的价值和重量，计算出每个物品的单位价值，最后调用`solve_knapsack`函数求解0-1背包问题并输出最大价值。