C语言求解0/1背包箱问题。分别用先进先出队列分支限界法和优先队列分支限界法实现。

首先，0/1背包问题是一种经典的动态规划问题，其思路是将问题分解成子问题，然后逐步求解。

先进先出队列分支限界法：

代码实现如下：

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

#define N 4
#define C 8

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

typedef struct {
    Node *queue[N * 10]; // 先进先出队列
    int front, rear;
} FIFO_Queue;

void init_queue(FIFO_Queue *q) {
    q->front = q->rear = 0;
}

int is_empty_queue(FIFO_Queue *q) {
    return q->front == q->rear;
}

int is_full_queue(FIFO_Queue *q) {
    return (q->rear + 1) % (N * 10) == q->front;
}

void enqueue(FIFO_Queue *q, Node *node) {
    if (!is_full_queue(q)) {
        q->queue[q->rear] = node;
        q->rear = (q->rear + 1) % (N * 10);
    }
}

Node *dequeue(FIFO_Queue *q) {
    if (!is_empty_queue(q)) {
        Node *node = q->queue[q->front];
        q->front = (q->front + 1) % (N * 10);
        return node;
    }
    return NULL;
}

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 用于排序的比较函数
int cmp_node(const void *a, const void *b) {
    Node *n1 = *(Node **)a;
    Node *n2 = *(Node **)b;
    return n2->bound - n1->bound;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int knapsack(int *weight, int *profit, int n) {
    FIFO_Queue queue;
    init_queue(&queue);

    Node *root = (Node *)malloc(sizeof(Node));
    root->level = root->profit = root->weight = 0;
    root->bound = 0;

    int max_profit = 0;

    enqueue(&queue, root);

    while (!is_empty_queue(&queue)) {
        Node *node = dequeue(&queue);

        if (node->level == n) {
            if (node->profit > max_profit) {
                max_profit = node->profit;
            }
            continue;
        }

        Node *left = (Node *)malloc(sizeof(Node));
        left->level = node->level + 1;
        left->profit = node->profit + profit[left->level - 1];
        left->weight = node->weight + weight[left->level - 1];

        if (left->weight <= C && left->profit > max_profit) {
            max_profit = left->profit;
        }

        if (left->bound > max_profit) {
            enqueue(&queue, left);
        }

        Node *right = (Node *)malloc(sizeof(Node));
        right->level = node->level + 1;
        right->profit = node->profit;
        right->weight = node->weight;

        if (right->bound > max_profit) {
            enqueue(&queue, right);
        }
    }

    return max_profit;
}

int main() {
    int weight[N] = {2, 3, 4, 5};
    int profit[N] = {3, 4, 5, 6};

    printf("最大价值为：%d\n", knapsack(weight, profit, N));

    return 0;
}

优先队列分支限界法：

代码实现如下：

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

#define N 4
#define C 8

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

typedef struct {
    Node **queue; // 优先队列
    int size;
} PQ;

void init_pq(PQ *pq) {
    pq->queue = (Node **)malloc(N * sizeof(Node *));
    pq->size = 0;
}

int is_empty_pq(PQ *pq) {
    return pq->size == 0;
}

void enqueue(PQ *pq, Node *node) {
    pq->queue[pq->size++] = node;
}

Node *dequeue(PQ *pq) {
    int min_idx = 0;
    for (int i = 1; i < pq->size; i++) {
        if (pq->queue[i]->bound > pq->queue[min_idx]->bound) {
            min_idx = i;
        }
    }
    Node *node = pq->queue[min_idx];
    pq->queue[min_idx] = pq->queue[pq->size - 1];
    pq->size--;
    return node;
}

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 用于排序的比较函数
int cmp_node(const void *a, const void *b) {
    Node *n1 = *(Node **)a;
    Node *n2 = *(Node **)b;
    return n2->bound - n1->bound;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int bound(Node *node, int *weight, int *profit, int n) {
    if (node->weight >= C) {
        return 0;
    }

    int j = node->level;
    int totweight = node->weight;
    int result = node->profit;

    while (j < n && totweight + weight[j] <= C) {
        totweight += weight[j];
        result += profit[j];
        j++;
    }

    if (j < n) {
        result += (C - totweight) * profit[j] / weight[j];
    }

    return result;
}

int knapsack(int *weight, int *profit, int n) {
    PQ pq;
    init_pq(&pq);

    Node *root = (Node *)malloc(sizeof(Node));
    root->level = root->profit = root->weight = 0;
    root->bound = bound(root, weight, profit, n);

    int max_profit = 0;

    enqueue(&pq, root);

    while (!is_empty_pq(&pq)) {
        Node *node = dequeue(&pq);

        if (node->level == n) {
            if (node->profit > max_profit) {
                max_profit = node->profit;
            }
            continue;
        }

        Node *left = (Node *)malloc(sizeof(Node));
        left->level = node->level + 1;
        left->profit = node->profit + profit[left->level - 1];
        left->weight = node->weight + weight[left->level - 1];
        left->bound = bound(left, weight, profit, n);

        if (left->weight <= C && left->profit > max_profit) {
            max_profit = left->profit;
        }

        if (left->bound > max_profit) {
            enqueue(&pq, left);
        }

        Node *right = (Node *)malloc(sizeof(Node));
        right->level = node->level + 1;
        right->profit = node->profit;
        right->weight = node->weight;
        right->bound = bound(right, weight, profit, n);

        if (right->bound > max_profit) {
            enqueue(&pq, right);
        }
    }

    return max_profit;
}

int main() {
    int weight[N] = {2, 3, 4, 5};
    int profit[N] = {3, 4, 5, 6};

    printf("最大价值为：%d\n", knapsack(weight, profit, N));

    return 0;
}