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

0/1背包问题指的是有一个固定容量的背包，一些物品和它们的价值，需要将物品放入背包中，使得背包能够装下的物品总价值最大。其中每个物品只能选择放入背包一次，即要么放入，要么不放入。

下面分别介绍先进先出队列分支限界法和优先队列分支限界法的实现。

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

#include <stdio.h>
#include <stdlib.h>
#define N 100

int n, c;
int v[N], w[N]; // 物品的价值和重量
int bestv; // 最优价值
int x[N], bestx[N]; // 当前解和最优解
typedef struct {
    int id;
    int cv;
    int cw;
    int bound;
} Node;

int cmp(const void *a, const void *b) { // 按照价值密度排序
    double r1 = ((Node *) a)->bound;
    double r2 = ((Node *) b)->bound;
    return r2 - r1 > 0 ? 1 : -1;
}

void knapsack() {
    int i, j, k;
    int q[N]; // 队列
    int head = 0, tail = 0;

    Node u, v;
    u.id = -1;
    u.cw = u.cv = 0;
    u.bound = 0;
    bestv = 0;
    q[tail++] = -1; // 根结点入队
    while (head != tail) {
        i = q[head++]; // 出队
        if (i == n - 1) continue; // 已经到达叶子结点
        // 左儿子节点
        v.id = i + 1;
        v.cw = u.cw + w[v.id];
        v.cv = u.cv + v[v.id];
        if (v.cw <= c && v.cv > bestv) { // 更新最优解
            bestv = v.cv;
            for (k = 0; k <= i; k++) bestx[k] = x[k];
            bestx[v.id] = 1;
        }
        v.bound = bound(v); // 计算价值上界
        if (v.bound > bestv) q[tail++] = v.id; // 进入左儿子结点
        // 右儿子结点
        v.cw = u.cw;
        v.cv = u.cv;
        v.bound = bound(v); // 计算价值上界
        if (v.bound > bestv) q[tail++] = v.id; // 进入右儿子结点
    }
}

double bound(Node u) { // 计算价值上界函数
    int j, k;
    int totW;
    double bound;
    if (u.cw >= c) return 0; // 超出容量，直接返回
    else {
        bound = u.cv;
        j = u.id + 1;
        totW = u.cw;
        while (j <= n - 1 && totW + w[j] <= c) { // 装满背包
            totW += w[j];
            bound += v[j];
            j++;
        }
        if (j <= n - 1) // 装满剩余空间的物品
            bound += (c - totW) * v[j] / w[j];
        return bound;
    }
}

int main() {
    int i;
    scanf("%d%d", &n, &c);
    for (i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]);
    knapsack();
    printf("%d\n", bestv);
    return 0;
}

优先队列分支限界法：

#include <stdio.h>
#include <stdlib.h>
#define N 100

int n, c;
int v[N], w[N]; // 物品的价值和重量
int bestv; // 最优价值
int x[N], bestx[N]; // 当前解和最优解
typedef struct {
    int id;
    int cv;
    int cw;
    int bound;
} Node;

int cmp(const void *a, const void *b) { // 按照价值密度排序
    double r1 = ((Node *) a)->bound;
    double r2 = ((Node *) b)->bound;
    return r2 - r1 > 0 ? 1 : -1;
}

void knapsack() {
    int i, j, k;
    int q[N]; // 队列
    int head = 0, tail = 0;

    Node u, v;
    u.id = -1;
    u.cw = u.cv = 0;
    u.bound = 0;
    bestv = 0;
    q[tail++] = -1; // 根结点入队
    while (head != tail) {
        i = q[head++]; // 出队
        if (i == n - 1) continue; // 已经到达叶子结点
        // 左儿子节点
        v.id = i + 1;
        v.cw = u.cw + w[v.id];
        v.cv = u.cv + v[v.id];
        if (v.cw <= c && v.cv > bestv) { // 更新最优解
            bestv = v.cv;
            for (k = 0; k <= i; k++) bestx[k] = x[k];
            bestx[v.id] = 1;
        }
        v.bound = bound(v); // 计算价值上界
        if (v.bound > bestv) {
            q[tail++] = v.id; // 进入左儿子结点
            qsort(q + head, tail - head, sizeof(int), cmp); // 按照价值密度排序
        }
        // 右儿子结点
        v.cw = u.cw;
        v.cv = u.cv;
        v.bound = bound(v); // 计算价值上界
        if (v.bound > bestv) {
            q[tail++] = v.id; // 进入右儿子结点
            qsort(q + head, tail - head, sizeof(int), cmp); // 按照价值密度排序
        }
    }
}

double bound(Node u) { // 计算价值上界函数
    int j, k;
    int totW;
    double bound;
    if (u.cw >= c) return 0; // 超出容量，直接返回
    else {
        bound = u.cv;
        j = u.id + 1;
        totW = u.cw;
        while (j <= n - 1 && totW + w[j] <= c) { // 装满背包
            totW += w[j];
            bound += v[j];
            j++;
        }
        if (j <= n - 1) // 装满剩余空间的物品
            bound += (c - totW) * v[j] / w[j];
        return bound;
    }
}

int main() {
    int i;
    scanf("%d%d", &n, &c);
    for (i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]);
    knapsack();
    printf("%d\n", bestv);
    return 0;
}