c语言0－1背包问题(优先队列式分支限界法)

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

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

#define MAX_N 1000

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

typedef struct {
    int level; // 当前节点所在的层数
    int profit; // 当前节点的价值上界
    int weight; // 当前节点的重量
} Node;

typedef struct {
    Node *data[MAX_N]; // 优先队列
    int size; // 优先队列中元素的个数
} PriorityQueue;

// 初始化优先队列
void init(PriorityQueue *q) {
    q->size = 0;
}

// 判断优先队列是否为空
int is_empty(PriorityQueue *q) {
    return q->size == 0;
}

// 判断优先队列是否已满
int is_full(PriorityQueue *q) {
    return q->size == MAX_N;
}

// 获取优先队列中优先级最高的节点
Node *get_highest_priority_node(PriorityQueue *q) {
    int i, highest_priority_index = 0;
    for (i = 1; i < q->size; i++) {
        if (q->data[i]->profit > q->data[highest_priority_index]->profit) {
            highest_priority_index = i;
        }
    }
    Node *highest_priority_node = q->data[highest_priority_index];
    // 将优先级最高的节点从优先队列中删除
    q->data[highest_priority_index] = q->data[q->size - 1];
    q->size--;
    return highest_priority_node;
}

// 将节点插入优先队列中
void insert_node(PriorityQueue *q, Node *node) {
    if (is_full(q)) {
        printf("Priority queue is full.\n");
        exit(1);
    }
    q->data[q->size++] = node;
}

// 计算价值上界
int bound(Item *items, int n, int capacity, int level, int weight, int profit) {
    if (weight >= capacity) {
        return 0;
    }
    int i, bound = profit;
    int remaining_capacity = capacity - weight;
    for (i = level; i < n; i++) {
        if (items[i].w <= remaining_capacity) {
            bound += items[i].v;
            remaining_capacity -= items[i].w;
        } else {
            bound += items[i].v * ((double) remaining_capacity / items[i].w);
            break;
        }
    }
    return bound;
}

// 优先队列式分支限界法求解0-1背包问题
int knapsack(Item *items, int n, int capacity) {
    PriorityQueue q;
    init(&q);
    Node *root = (Node *) malloc(sizeof(Node));
    root->level = -1;
    root->profit = 0;
    root->weight = 0;
    insert_node(&q, root);
    int max_profit = 0;
    while (!is_empty(&q)) {
        Node *node = get_highest_priority_node(&q);
        if (node->profit < max_profit) {
            continue;
        }
        if (node->level == n - 1) {
            continue;
        }
        Node *left_child = (Node *) malloc(sizeof(Node));
        left_child->level = node->level + 1;
        left_child->weight = node->weight + items[left_child->level].w;
        left_child->profit = node->profit + items[left_child->level].v;
        if (left_child->weight <= capacity && left_child->profit > max_profit) {
            max_profit = left_child->profit;
        }
        left_child->profit = bound(items, n, capacity, left_child->level + 1, left_child->weight, left_child->profit);
        if (left_child->profit > max_profit) {
            insert_node(&q, left_child);
        } else {
            free(left_child);
        }
        Node *right_child = (Node *) malloc(sizeof(Node));
        right_child->level = node->level + 1;
        right_child->weight = node->weight;
        right_child->profit = node->profit;
        right_child->profit = bound(items, n, capacity, right_child->level + 1, right_child->weight, right_child->profit);
        if (right_child->profit > max_profit) {
            insert_node(&q, right_child);
        } else {
            free(right_child);
        }
    }
    return max_profit;
}

int main() {
    Item items[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(items) / sizeof(Item);
    int capacity = 50;
    int max_profit = knapsack(items, n, capacity);
    printf("Max profit: %d\n", max_profit);

    return 0;
}