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

0/1背包问题是一个经典的动态规划问题，不过这里我们将使用分支限界法来解决它。分支限界法是一种求解最优化问题的通用方法，它通过不断地分割问题空间，缩小可行解的范围，最终找到最优解。

下面我们将分别介绍使用先进先出队列和优先队列的分支限界法求解0/1背包问题，并提供相应的C语言代码实现。

先进先出队列分支限界法

先进先出队列分支限界法是一种简单的分支限界算法，它的核心思想是将所有的未扩展节点按照它们进入队列的时间顺序进行排列。在每次扩展节点时，选择队列中最早加入的节点进行扩展。这种方法的优点是实现简单，但是可能会导致算法效率较低。

下面是使用先进先出队列分支限界法解决0/1背包问题的C语言代码实现：

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

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

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

// 节点结构体
typedef struct {
    int level;        // 节点所在的层数
    int profit;       // 当前已获得的总价值
    int weight;       // 当前已装入的物品总重量
    int bound;        // 当前节点的价值上界
} node;

// 先进先出队列
typedef struct {
    node *data[MAX_N]; // 队列中的节点
    int head;          // 队头
    int tail;          // 队尾
} queue;

// 初始化队列
void init_queue(queue *q) {
    q->head = 0;
    q->tail = 0;
}

// 判断队列是否为空
int is_empty(queue *q) {
    return q->head == q->tail;
}

// 判断队列是否已满
int is_full(queue *q) {
    return q->tail == MAX_N;
}

// 入队
void enqueue(queue *q, node *n) {
    if (is_full(q)) {
        printf("queue is full\n");
        return;
    }
    q->data[q->tail++] = n;
}

// 出队
node *dequeue(queue *q) {
    if (is_empty(q)) {
        printf("queue is empty\n");
        return NULL;
    }
    node *n = q->data[q->head++];
    return n;
}

// 计算节点的价值上界
int bound(node *n, int n_items, item *items, int capacity) {
    int i, j;
    int bound = n->profit;
    int tot_weight = n->weight;
    i = n->level + 1;
    while (i <= n_items && tot_weight + items[i].w <= capacity) {
        tot_weight += items[i].w;
        bound += items[i].v;
        i++;
    }
    if (i <= n_items) {
        bound += (capacity - tot_weight) * items[i].v / items[i].w;
    }
    return bound;
}

// 先进先出队列分支限界法求解0/1背包问题
int knapsack_bfs(int n_items, item *items, int capacity) {
    int i, max_profit = 0;
    node *root, *curr, *left, *right;
    queue q;
    init_queue(&q);

    // 初始化根节点
    root = (node*)malloc(sizeof(node));
    root->level = 0;
    root->profit = 0;
    root->weight = 0;
    root->bound = bound(root, n_items, items, capacity);

    // 将根节点入队
    enqueue(&q, root);

    while (!is_empty(&q)) {
        // 取出队头节点
        curr = dequeue(&q);

        // 如果当前节点的价值上界小于当前的最大价值，则不再扩展
        if (curr->bound <= max_profit) {
            continue;
        }

        // 如果当前节点是叶子节点，则更新最大价值
        if (curr->level == n_items) {
            if (curr->profit > max_profit) {
                max_profit = curr->profit;
            }
            continue;
        }

        // 扩展左子树节点
        left = (node*)malloc(sizeof(node));
        left->level = curr->level + 1;
        left->profit = curr->profit + items[left->level].v;
        left->weight = curr->weight + items[left->level].w;
        left->bound = bound(left, n_items, items, capacity);

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

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

        // 扩展右子树节点
        right = (node*)malloc(sizeof(node));
        right->level = curr->level + 1;
        right->profit = curr->profit;
        right->weight = curr->weight;
        right->bound = bound(right, n_items, items, capacity);

        if (right->weight <= capacity && right->profit > max_profit) {
            max_profit = right->profit;
        }

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

    return max_profit;
}

int main() {
    int n_items, capacity, i, max_profit;
    item items[MAX_N];

    // 读入物品数和背包容量
    scanf("%d%d", &n_items, &capacity);

    // 读入每个物品的重量和价值
    for (i = 1; i <= n_items; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
    }

    // 使用先进先出队列分支限界法求解0/1背包问题
    max_profit = knapsack_bfs(n_items, items, capacity);

    // 输出最大价值
    printf("%d\n", max_profit);

    return 0;
}

优先队列分支限界法

优先队列分支限界法是一种效率更高的分支限界算法，它的核心思想是将所有的未扩展节点按照它们的价值上界进行排列。在每次扩展节点时，选择价值上界最大的节点进行扩展。这种方法的优点是可以更快地找到最优解，但是实现相对复杂一些。

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

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

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

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

// 节点结构体
typedef struct {
    int level;        // 节点所在的层数
    int profit;       // 当前已获得的总价值
    int weight;       // 当前已装入的物品总重量
    int bound;        // 当前节点的价值上界
} node;

// 优先队列
typedef struct {
    node *data[MAX_N]; // 队列中的节点
    int size;          // 队列中的节点数
} priority_queue;

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

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

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

// 入队
void enqueue(priority_queue *q, node *n) {
    int i, j;
    if (is_full(q)) {
        printf("queue is full\n");
        return;
    }
    i = q->size++;
    j = (i - 1) / 2;
    while (i > 0 && q->data[j]->bound <= n->bound) {
        q->data[i] = q->data[j];
        i = j;
        j = (i - 1) / 2;
    }
    q->data[i] = n;
}

// 出队
node *dequeue(priority_queue *q) {
    int i, j, k;
    if (is_empty(q)) {
        printf("queue is empty\n");
        return NULL;
    }
    node *n = q->data[0];
    q->size--;
    if (q->size == 0) {
        return n;
    }
    q->data[0] = q->data[q->size];
    i = 0;
    j = 1;
    while (j < q->size) {
        if (j + 1 < q->size && q->data[j + 1]->bound > q->data[j]->bound) {
            k = j + 1;
        } else {
            k = j;
        }
        if (q->data[k]->bound <= q->data[i]->bound) {
            break;
        }
        node *temp = q->data[k];
        q->data[k] = q->data[i];
        q->data[i] = temp;
        i = k;
        j = 2 * i + 1;
    }
    return n;
}

// 计算节点的价值上界
int bound(node *n, int n_items, item *items, int capacity) {
    int i, j;
    int bound = n->profit;
    int tot_weight = n->weight;
    i = n->level + 1;
    while (i <= n_items && tot_weight + items[i].w <= capacity) {
        tot_weight += items[i].w;
        bound += items[i].v;
        i++;
    }
    if (i <= n_items) {
        bound += (capacity - tot_weight) * items[i].v / items[i].w;
    }
    return bound;
}

// 优先队列分支限界法求解0/1背包问题
int knapsack_pq(int n_items, item *items, int capacity) {
    int i, max_profit = 0;
    node *root, *curr, *left, *right;
    priority_queue q;
    init_priority_queue(&q);

    // 初始化根节点
    root = (node*)malloc(sizeof(node));
    root->level = 0;
    root->profit = 0;
    root->weight = 0;
    root->bound = bound(root, n_items, items, capacity);

    // 将根节点入队
    enqueue(&q, root);

    while (!is_empty(&q)) {
        // 取出队头节点
        curr = dequeue(&q);

        // 如果当前节点的价值上界小于当前的最大价值，则不再扩展
        if (curr->bound <= max_profit) {
            continue;
        }

        // 如果当前节点是叶子节点，则更新最大价值
        if (curr->level == n_items) {
            if (curr->profit > max_profit) {
                max_profit = curr->profit;
            }
            continue;
        }

        // 扩展左子树节点
        left = (node*)malloc(sizeof(node));
        left->level = curr->level + 1;
        left->profit = curr->profit + items[left->level].v;
        left->weight = curr->weight + items[left->level].w;
        left->bound = bound(left, n_items, items, capacity);

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

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

        // 扩展右子树节点
        right = (node*)malloc(sizeof(node));
        right->level = curr->level + 1;
        right->profit = curr->profit;
        right->weight = curr->weight;
        right->bound = bound(right, n_items, items, capacity);

        if (right->weight <= capacity && right->profit > max_profit) {
            max_profit = right->profit;
        }

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

    return max_profit;
}

int main() {
    int n_items, capacity, i, max_profit;
    item items[MAX_N];

    // 读入物品数和背包容量
    scanf("%d%d", &n_items, &capacity);

    // 读入每个物品的重量和价值
    for (i = 1; i <= n_items; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
    }

    // 使用优先队列分支限界法求解0/1背包问题
    max_profit = knapsack_pq(n_items, items, capacity);

    // 输出最大价值
    printf("%d\n", max_profit);

    return 0;
}