C++分支限界算法详解（从零开始掌握分支限界法）

什么是分支限界法？

分支限界法（Branch and Bound）是一种系统化搜索解空间的方法，常用于求解最优化问题，如旅行商问题（TSP）、0-1背包问题、任务分配等。

其核心思想是：

• 分支（Branch）：将问题分解为若干子问题（即生成子节点）；
• 限界（Bound）：为每个子问题计算一个“界限值”（如当前路径的最小可能代价），若该界限值已劣于当前已知最优解，则剪枝（不再继续探索）。

与回溯法不同，分支限界通常使用队列或优先队列（如最小堆）来管理待探索的节点，确保优先探索最有希望的路径。

分支限界 vs 回溯法

虽然两者都涉及递归和剪枝，但关键区别在于：

实战：用C++实现0-1背包问题的分支限界解法

我们以经典的0-1背包问题为例：给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求能装入的最大总价值。

我们将使用优先队列（最大堆）按“当前价值 + 剩余物品上界”排序，优先探索最有希望的节点。

#include <iostream>#include <queue>#include <algorithm>using namespace std;struct Item {    int weight, value;};struct Node {    int level;        // 当前考虑第几个物品    int profit;       // 当前总价值    int weight;       // 当前总重量    double bound;     // 上界估计值    bool operator<(const Node& other) const {        return bound < other.bound; // 最大堆：bound大的优先    }};double calculateBound(Node u, int n, int W, vector<Item>& items) {    if (u.weight >= W) return 0;        double bound = u.profit;    int j = u.level + 1;    int totalWeight = u.weight;    while (j < n && totalWeight + items[j].weight <= W) {        totalWeight += items[j].weight;        bound += items[j].value;        j++;    }    if (j < n) {        bound += (W - totalWeight) * ((double)items[j].value / items[j].weight);    }    return bound;}int knapsackBranchAndBound(int W, vector<Item>& items) {    int n = items.size();    sort(items.begin(), items.end(), [](Item a, Item b) {        return (double)a.value / a.weight > (double)b.value / b.weight;    });    priority_queue<Node> pq;    Node root = { -1, 0, 0, 0.0 };    root.bound = calculateBound(root, n, W, items);    pq.push(root);    int maxProfit = 0;    while (!pq.empty()) {        Node u = pq.top();        pq.pop();        if (u.bound > maxProfit && u.level < n - 1) {            Node v;            v.level = u.level + 1;            // 包含当前物品            v.weight = u.weight + items[v.level].weight;            v.profit = u.profit + items[v.level].value;            if (v.weight <= W && v.profit > maxProfit) {                maxProfit = v.profit;            }            v.bound = calculateBound(v, n, W, items);            if (v.bound > maxProfit) {                pq.push(v);            }            // 不包含当前物品            v.weight = u.weight;            v.profit = u.profit;            v.bound = calculateBound(v, n, W, items);            if (v.bound > maxProfit) {                pq.push(v);            }        }    }    return maxProfit;}int main() {    int W = 50;    vector<Item> items = { {10, 60}, {20, 100}, {30, 120} };    cout << "最大价值: " << knapsackBranchAndBound(W, items) << endl;    return 0;}

代码解析

• Node 结构体保存当前状态（层级、利润、重量、上界）；
• calculateBound 函数使用贪心策略估算剩余物品能带来的最大价值（即“上界”）；
• 主函数中，先按单位价值降序排序物品，提高剪枝效率；
• 优先队列确保每次扩展最有希望的节点，实现C++算法优化。

总结

通过本教程，你已经掌握了C++分支限界算法的基本原理与实现方法。记住，分支限界法的关键在于：

1. 合理设计“上界”函数；
2. 使用合适的数据结构（如优先队列）管理搜索顺序；
3. 及时剪枝，避免无效搜索。

无论是面试还是竞赛，回溯与剪枝技巧都是提升算法效率的核心。多加练习，你也能写出高效的分支限界法教程级代码！

—— 学完记得动手实践哦！——