优先队列求0-1背包c语言输出最优解

以下是使用优先队列求解0-1背包问题并输出最优解的C语言代码：

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

// 优先队列结构体
typedef struct {
    int value;  // 节点价值
    int weight;  // 节点重量
    int level;  // 节点层数
} Node;

// 用于比较节点优先级的函数
int cmp(const void* a, const void* b) {
    const Node* nodeA = (const Node*)a;
    const Node* nodeB = (const Node*)b;
    double priorityA = (double)nodeA->value / nodeA->weight;
    double priorityB = (double)nodeB->value / nodeB->weight;
    if (priorityA < priorityB) {
        return 1;
    } else if (priorityA > priorityB) {
        return -1;
    } else {
        return 0;
    }
}

// 求解0-1背包问题并输出最优解
void knapsack(int n, int capacity, int* values, int* weights) {
    // 初始化优先队列
    Node* queue = (Node*)malloc(n * sizeof(Node));
    for (int i = 0; i < n; i++) {
        queue[i].value = values[i];
        queue[i].weight = weights[i];
        queue[i].level = 0;
    }
    qsort(queue, n, sizeof(Node), cmp);

    // 初始化最优解
    int bestValue = 0;
    int* bestItems = (int*)calloc(n, sizeof(int));

    // 迭代搜索
    while (1) {
        // 取出队首节点
        Node node = queue[0];
        if (node.level == n) {  // 搜索到叶子节点
            if (node.value > bestValue) {
                bestValue = node.value;
                for (int i = 0; i < n; i++) {
                    bestItems[i] = (node.weight >> i) & 1;
                }
            }
        } else {
            // 扩展左儿子节点（不选当前物品）
            Node left = node;
            left.level = node.level + 1;
            left.weight -= weights[left.level - 1];
            queue[0] = left;
            qsort(queue, n, sizeof(Node), cmp);

            // 扩展右儿子节点（选当前物品）
            Node right = node;
            right.level = node.level + 1;
            queue[n - 1] = right;
            qsort(queue, n, sizeof(Node), cmp);
        }

        // 判断是否需要终止搜索
        if (queue[0].value + (capacity - queue[0].weight) * (double)queue[0].value / queue[0].weight <= bestValue) {
            break;
        }
    }

    // 输出最优解
    printf("Best value: %d\n", bestValue);
    printf("Best items: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestItems[i]);
    }
    printf("\n");

    // 释放内存
    free(queue);
    free(bestItems);
}

// 测试
int main() {
    int n = 5;
    int capacity = 10;
    int values[] = {6, 3, 5, 4, 6};
    int weights[] = {2, 2, 6, 5, 4};
    knapsack(n, capacity, values, weights);
    return 0;
}

该代码使用优先队列来实现分支限界搜索，利用贪心算法对节点进行排序，每次取出优先级最高的节点进行扩展。在搜索过程中，维护当前最优解，并在搜索结束后输出最优解。