C语言分支限界法解决0-1背包问题

0-1背包问题是经典的动态规划问题，但也可以使用分支限界法进行求解。 具体思路如下： 1.定义一个结构体Node，存储每个节点的信息，包括当前物品价值、重量、价值密度、剩余空间、上界价值和已选物品等信息。 2.将第一个节点加入优先队列，然后不断取出队列中价值最高的节点进行扩展，即生成其左右儿子节点。 3.对于左儿子节点，考虑将下一个物品放入背包中，更新节点信息，计算其上界价值并加入优先队列。对于右儿子节点，考虑不放下一个物品，直接加入优先队列。 4.重复步骤2和3，直到队列为空或者所有节点都被扩展过。 5.在扩展过程中，记录下最优解。 下面是C语言实现代码： ```c #include <stdio.h> #include <stdlib.h> #define MAX_N 100 typedef struct Node { int v; // 当前价值 int w; // 当前重量 double d; // 当前价值密度 int u; // 剩余空间 int b; // 已选物品 double up;// 上界价值 }Node; int n, W, ans; // 物品数目、背包容量、最优解 int w[MAX_N], v[MAX_N]; // 物品重量、价值 Node pq[MAX_N * MAX_N]; // 优先队列 int cmp(const void* a, const void* b) { Node* p = (Node*)a; Node* q = (Node*)b; return (q->up - p->up) > 0; } void init() { ans = 0; scanf("%d%d", &n, &W); for (int i = 0; i < n; i++) { scanf("%d%d", &w[i], &v[i]); } } void solve() { Node u, v; u.v = u.w = u.u = u.b = 0; double max = 0; for (int i = 0; i < n; i++) { u.up += v[i]; } pq[0] = u; int r = 1; while (r > 0) { u = pq[0]; pq[0] = pq[--r]; qsort(pq, r, sizeof(pq[0]), cmp); if (u.u >= w[u.b] && u.b < n) { v.b = u.b + 1; v.u = u.u - w[u.b]; v.w = u.w + w[u.b]; v.v = u.v + v[u.b]; v.d = v.v * 1.0 / v.w; v.up = v.v; for (int i = v.b; i < n; i++) { if (v.u < w[i]) { v.up += v.d * v.u; break; } else { v.up += v[i]; v.u -= w[i]; } } if (v.up > max) { pq[r++] = v; max = v.up; } } u.up -= v[u.b]; if (u.up > max && u.b < n) { v.u = u.u; v.w = u.w; v.v = u.v; v.b = u.b + 1; v.d = v.v * 1.0 / v.w; v.up = v.v; for (int i = v.b; i < n; i++) { if (v.u < w[i]) { v.up += v.d * v.u; break; } else { v.up += v[i]; v.u -= w[i]; } } if (v.up > max) { pq[r++] = v; max = v.up; } } if (u.v > ans) { ans = u.v; } } } void output() { printf("%d\n", ans); } int main() { init(); solve(); output(); return 0; } ```