分支限界法求解01背包C语言

### 分支限界法求解01背包问题的C语言实现 分支限界法是一种用于解决组合优化问题的有效算法，特别适用于求解01背包问题。在该方法中，通过构建搜索树并结合优先队列来选择最有希望的结点进行扩展，从而减少不必要的搜索路径[^3]。 以下是使用C语言实现分支限界法求解01背包问题的代码示例： ```c #include <stdio.h> #include <stdlib.h> typedef struct { int id; // 物品编号 float weight; // 物品重量 float value; // 物品价值 float density; // 单位重量价值 } Object; // 比较函数，用于计算单位重量价值并排序 int compare(const void *a, const void *b) { return ((Object *)b)->density - ((Object *)a)->density; } // 计算上界（估计值） float bound(int i, int n, float capacity, float totalValue, float totalWeight, Object objects[]) { if (totalWeight >= capacity) return 0; float b = totalValue; while (i < n && objects[i].weight <= capacity - totalWeight) { totalWeight += objects[i].weight; b += objects[i].value; i++; } if (i < n) { b += (capacity - totalWeight) * objects[i].density; } return b; } // 分支限界法主函数 void knapsack(int n, float capacity, Object objects[], int bestX[], float *bestValue) { qsort(objects, n, sizeof(Object), compare); // 按单位重量价值排序 int *include = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) include[i] = 0; float totalWeight = 0, totalValue = 0; int i = 0; while (i >= 0) { if (i < n) { if (totalWeight + objects[i].weight <= capacity) { // 包括第i个物品 include[i] = 1; totalWeight += objects[i].weight; totalValue += objects[i].value; if (bound(i + 1, n, capacity, totalValue, totalWeight, objects) > *bestValue) { i++; } else { if (totalValue > *bestValue) { *bestValue = totalValue; for (int j = 0; j < n; j++) bestX[j] = include[j]; } include[i] = 0; totalWeight -= objects[i].weight; totalValue -= objects[i].value; } } else { include[i] = 0; } } if (i < n && include[i] == 0) { // 不包括第i个物品 if (bound(i + 1, n, capacity, totalValue, totalWeight, objects) > *bestValue) { i++; } else { if (totalValue > *bestValue) { *bestValue = totalValue; for (int j = 0; j < n; j++) bestX[j] = include[j]; } i--; if (i >= 0) { totalWeight -= objects[i].weight * include[i]; totalValue -= objects[i].value * include[i]; } } } else { i--; if (i >= 0) { totalWeight -= objects[i].weight * include[i]; totalValue -= objects[i].value * include[i]; } } } free(include); } int main() { int n = 4; // 物品数量 float capacity = 15; // 背包容量 Object objects[] = { {0, 2, 10, 5}, {1, 5, 20, 4}, {2, 10, 30, 3}, {3, 5, 15, 3} }; for (int i = 0; i < n; i++) objects[i].density = objects[i].value / objects[i].weight; int bestX[n]; // 最优解向量 float bestValue = 0; // 最优价值 knapsack(n, capacity, objects, bestX, &bestValue); printf("最优价值: %.2f\n", bestValue); printf("最优解向量: "); for (int i = 0; i < n; i++) printf("%d ", bestX[i]); printf("\n"); return 0; } ``` 上述代码实现了分支限界法的核心逻辑，包括对物品按单位重量价值排序、计算上界以及通过递归方式进行搜索等步骤[^1]。 ### 算法核心思想 - **单位重量价值排序**：为了提高搜索效率，首先将所有物品按照单位重量价值从高到低排序[^3]。 - **上界计算**：通过贪心算法的思想计算当前结点的上界，即在剩余容量允许的情况下尽可能多地装入后续物品，以估计可能达到的最大价值[^2]。 - **剪枝策略**：当某个结点的上界小于当前已知的最佳解时，直接舍弃该结点及其子树，避免无效搜索。