用分支限界法求解装载问题，用优先队列式求解c语言

装载问题是一个经典的组合优化问题，其目标是在有限的容量下尽可能多地装载物品。分支限界法是一种常用的解决组合优化问题的算法，可以用来求解装载问题。

以下是使用优先队列式分支限界法求解装载问题的C语言代码：

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

using namespace std;

const int MAX_N = 100; // 最大物品数
const int MAX_C = 1000; // 最大容量

int N, C; // 物品数、容量
int w[MAX_N]; // 物品重量
int best; // 目前最优解
int cnt; // 记录扩展结点数

struct Node {
    int level; // 扩展结点所在的层数（即装入的物品数）
    int weight; // 当前已经装载的重量
    int value; // 当前已经装载的价值
    bool operator<(const Node& n) const { // 定义优先级队列的比较方式
        return value < n.value;
    }
};

priority_queue<Node> PQ; // 优先级队列

// 计算下界
int bound(int level, int weight, int value) {
    int bound = value;
    for (int i = level; i < N; i++) {
        if (weight + w[i] <= C) {
            weight += w[i];
            bound += w[i];
        } else {
            bound += (C - weight) * 1.0 / w[i] * value;
            break;
        }
    }
    return bound;
}

// 分支限界法求解
void solve() {
    Node u, v;
    u.level = u.weight = u.value = 0; // 根结点
    PQ.push(u);
    while (!PQ.empty()) {
        u = PQ.top();
        PQ.pop();
        if (u.value < best) {
            continue;
        }
        if (u.level == N) {
            best = u.value;
            continue;
        }
        cnt++;
        v.level = u.level + 1;
        v.weight = u.weight + w[v.level - 1];
        v.value = u.value + w[v.level - 1];
        if (v.weight <= C && v.value > best) {
            best = v.value;
        }
        if (bound(v.level, v.weight, v.value) > best) {
            PQ.push(v); // 左儿子结点入队
        }
        v.weight = u.weight;
        v.value = u.value;
        if (bound(v.level, v.weight, v.value) > best) {
            PQ.push(v); // 右儿子结点入队
        }
    }
}

int main() {
    scanf("%d %d", &N, &C);
    for (int i = 0; i < N; i++) {
        scanf("%d", &w[i]);
    }
    best = 0;
    solve();
    printf("最优解：%d\n", best);
    printf("扩展结点数：%d\n", cnt);
    return 0;
}

在代码中，我们使用一个优先级队列来维护当前扩展结点的集合，每次从中选取价值最大的结点进行扩展。在计算下界时，我们采用了一种贪心策略，即将剩余容量装满当前价值最高的物品。对于每个扩展结点，我们都生成两个子结点，一个是装入当前物品的子结点，另一个是不装入当前物品的子结点。如果一个子结点的下界大于目前的最优解，就将其加入优先级队列中，否则就剪枝。最终，当队列为空时，我们就得到了最优解。