C语言分支限界法求解0/1背包问题

### C语言分支限界法实现0-1背包问题 在C语言中，使用分支限界法解决0-1背包问题的核心思想是构建状态空间树，并通过限界函数剪枝以减少不必要的搜索路径[^4]。以下是具体的实现方法和代码示例。 #### 代码实现 ```c #include <stdio.h> #include <stdlib.h> #define MAX_N 100 // 最大物品数量 #define MAX_C 1000 // 最大背包容量 typedef struct { int value; // 物品价值 int weight; // 物品重量 double ratio; // 价值密度 (value/weight) } Item; typedef struct { int level; // 当前节点的层数 int value; // 当前节点的总价值 int weight; // 当前节点的总重量 int bound_value; // 当前节点的上界值 } Node; // 计算上界函数 int bound(Node node, int n, Item items[], int max_weight) { if (node.weight >= max_weight) { return 0; } int total_value = node.value; int total_weight = node.weight; for (int i = node.level; i < n; i++) { if (total_weight + items[i].weight <= max_weight) { total_weight += items[i].weight; total_value += items[i].value; } else { total_value += (max_weight - total_weight) * (items[i].value / items[i].weight); break; } } return total_value; } // 比较函数：按价值密度降序排序 int compare(const void *a, const void *b) { Item item1 = *(Item *)a; Item item2 = *(Item *)b; return (item2.ratio > item1.ratio) ? 1 : -1; } // 分支限界法主函数 void branch_and_bound(int n, int max_weight, Item items[]) { qsort(items, n, sizeof(Item), compare); // 按价值密度排序 Node queue[MAX_N]; // 队列用于存储节点 int front = 0, rear = 0; Node u, v; u.level = -1; // 初始化根节点 u.value = 0; u.weight = 0; u.bound_value = bound(u, n, items, max_weight); queue[rear++] = u; // 根节点入队 int max_value = 0; while (front < rear) { u = queue[front++]; if (u.level == -1) { v.level = 0; } else { v.level = u.level + 1; } // 左子节点（选择当前物品） if (v.level < n) { v.weight = u.weight + items[v.level].weight; v.value = u.value + items[v.level].value; if (v.weight <= max_weight && v.value > max_value) { max_value = v.value; } v.bound_value = bound(v, n, items, max_weight); if (v.bound_value > max_value) { queue[rear++] = v; } } // 右子节点（不选择当前物品） v.weight = u.weight; v.value = u.value; v.bound_value = bound(v, n, items, max_weight); if (v.bound_value > max_value) { queue[rear++] = v; } } printf("最大价值为: %d\n", max_value); } int main() { int n, max_weight; printf("请输入物品数量和背包容量: "); scanf("%d %d", &n, &max_weight); Item items[n]; printf("请输入每个物品的重量和价值:\n"); for (int i = 0; i < n; i++) { scanf("%d %d", &items[i].weight, &items[i].value); items[i].ratio = (double)items[i].value / items[i].weight; } branch_and_bound(n, max_weight, items); return 0; } ``` #### 代码说明 1. **物品排序**：为了提高效率，首先对物品按照价值密度（`value/weight`）进行降序排序[^3]。 2. **节点结构**：定义了`Node`结构体，包含当前节点的层数、总价值、总重量以及上界值。 3. **上界计算**：通过`bound`函数计算每个节点的上界值，用于判断是否需要继续扩展该节点。 4. **队列操作**：使用队列存储待扩展的节点，优先扩展上界值较大的节点[^4]。 5. **剪枝策略**：如果某个节点的上界值小于当前已知的最大价值，则直接剪枝，避免无效搜索。 --- ###