优先队列求0-1背包C语言

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

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

#define MAX_N 1000
#define MAX_W 10000

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

// 优先队列结构体
typedef struct PriorityQueue {
    int size;           // 队列大小
    int items[MAX_N+1]; // 队列元素数组，下标从1开始
} PriorityQueue;

// 优先队列相关操作
PriorityQueue* createPriorityQueue() {
    PriorityQueue* q = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    q->size = 0;
    return q;
}

void push(PriorityQueue* q, int x) {
    int i = ++q->size;
    while (i > 1 && q->items[i/2] < x) {
        q->items[i] = q->items[i/2];
        i /= 2;
    }
    q->items[i] = x;
}

int pop(PriorityQueue* q) {
    int ret = q->items[1];
    int x = q->items[q->size--];
    int i = 1, j = 2;
    while (j <= q->size) {
        if (j < q->size && q->items[j] < q->items[j+1]) j++;
        if (q->items[j] <= x) break;
        q->items[i] = q->items[j];
        i = j; j = i*2;
    }
    q->items[i] = x;
    return ret;
}

int empty(PriorityQueue* q) {
    return q->size == 0;
}

// 0-1背包问题求解函数
int knapsack(int n, int w, Item* items) {
    PriorityQueue* q = createPriorityQueue();
    push(q, 0);  // 边界条件
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = w-items[i].w; j >= 0; j--) {
            if (!empty(q)) {
                int k = pop(q);
                if (k+j+items[i].w <= w) {
                    push(q, k+j+items[i].w);
                }
            }
        }
    }
    int ans = pop(q);
    free(q);
    return ans;
}

// 测试代码
int main() {
    int n = 3, w = 7;
    Item items[n] = {{3, 2}, {4, 3}, {2, 4}};
    int ans = knapsack(n, w, items);
    printf("ans = %d\n", ans);
    return 0;
}

该算法的时间复杂度为 O(n*w*log(n*w))，其中 n 表示物品数量，w 表示背包容量。