C++回溯与分支限界算法解决背包问题详解

算法思想对比

回溯法（Backtracking）与分支限界法（Branch and Bound）在解决组合优化问题时有着不同的设计逻辑，主要体现在求解目标和搜索方式两个维度：

• 求解目标不同：回溯法旨在找出解空间中满足约束条件的所有可行解，或者在可行解中寻优；而分支限界法则通常只要求找出一个满足约束的解，或在所有满足约束的解中，快速找到使目标函数（如价值）极大或极小的最优解。
• 搜索方式不同：回溯法对解空间进行深度优先搜索（DFS），通常使用递归栈来实现；分支限界法则以广度优先（BFS）或最小耗费优先的方式搜索，通常借助队列或优先队列来管理活结点表。

在实际应用中，若只需找到一个可行解且规模较小，回溯法较为直观；若在寻找全局最优解时希望尽早剪掉无效分支以提高效率，分支限界法的上限评估机制往往更具优势。

第1步：使用回溯法求解背包问题

目的：通过深度优先遍历所有物品取舍的组合，找到总价值最大的合法方案。

原理：定义一个递归函数 Backtrack(i, cp, cw)，其中 i 为当前考察的物品索引，cp 为当前累计价值，cw 为当前累计重量。

• 状态转移：对于第 i 个物品，尝试放入（x[i]=1）或不放入（x[i]=0）。
• 剪枝条件：仅在 cw + w[i] <= c（即装入后不超过背包容量）时，才递归进入下一层，否则该分支直接终止。
• 更新最优解：当递归到达叶子节点（i > n）时，若当前价值 cp 大于历史最大值 bestp，则更新 bestp 并记录当前的选取状态 bestx。

回溯法参考代码

#include <stdio.h>
int n, c, bestp;
int p[10000], w[10000], x[10000], bestx[10000];

void Backtrack(int i, int cp, int cw) {
    // 到达叶子节点，检查是否更新最优解
    if (i > n) {
        if (cp > bestp) {
            bestp = cp;
            for (int k = 1; k <= n; k++) 
                bestx[k] = x[k];
        }
    } else {
        // 尝试不选当前物品 (x[i] = 0)
        x[i] = 0;
        Backtrack(i + 1, cp, cw);
        
        // 尝试选择当前物品 (x[i] = 1)
        if (cw + w[i] <= c) {
            x[i] = 1;
            Backtrack(i + 1, cp + p[i], cw + w[i]);
        }
    }
}

int main() {
    printf("请输入背包最大容量:\n");
    scanf("%d", &c);
    printf("请输入物品个数:\n");
    scanf("%d", &n);
    
    // 输入物品的重量和价值
    for (int i = 1; i <= n; i++) {
        printf("请输入第 %d 个物品的重量和价值 (例如: 10 60):\n", i);
        scanf("%d %d", &w[i], &p[i]);
    }

    bestp = 0;
    Backtrack(1, 0, 0); // 从第一个物品开始搜索

    printf("最大价值为:%d\n", bestp);
    printf("被选中的物品依次是(0表示未选中，1表示选中):\n");
    for (int i = 1; i <= n; i++) 
        printf("%d ", bestx[i]);
    printf("\n");
    return 0;
}

以下为回溯法在标准测试用例下的运行结果示意：

第2步：使用分支限界法求解背包问题

目的：利用队列管理待扩展节点，通过计算“上界”（Upper Bound）来提前剔除不可能产生更优解的分支。

数据结构：节点结构体 nodetype 包含当前重量 w、价值 v、物品选择向量 x[] 以及最关键的上界 ub。

核心步骤：

1. 初始化：创建一个根节点加入队列，根节点代表尚未做出任何选择的状态。
2. 循环出队：取出队首节点 e，尝试生成其左孩子（选择当前物品）和右孩子（不选当前物品）。
3. 计算上界 bound()：对生成的子节点，估算在剩余容量下能获得的最大理论价值。若该上界不大于目前已知的最优解 bestv，则该节点及其子树可被剪枝（不再入队）。
4. 入队处理：对于左孩子，如果装满可行则直接计算价值并作为潜在解比较，不可行则不入队；对于右孩子，仅当其理论上有机会超越现有最优解时才入队。

分支限界法参考代码

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 100;
struct Item { int id, w, v; double ratio; } items[MAXN];

// 按性价比降序排序，这对计算紧确的上界至关重要
bool compareItems(Item a, Item b) {
    return a.ratio > b.ratio;
}

int n, c;
double bestV = 0; // 使用double防止精度损失影响判断
int bestX[MAXN];

struct Node {
    int depth;       // 决策深度
    double currentV; // 当前价值
    int currentW;    // 当前重量
    int upBound;     // 上界估值
    bool isSelected[MAXN]; // 路径记录
};

// 计算给定节点的最大可能价值（上界）
// 这里假设物品已按性价比排序，可以使用贪心填充剩余容量
int getUpBound(Node e) {
    double res = e.currentV;
    int remCap = c - e.currentW;
    // 从下一个物品开始贪心填满
    for (int i = e.depth + 1; i <= n; i++) {
        if (remCap >= items[i].w) {
            res += items[i].v;
            remCap -= items[i].w;
        } else {
            // 部分装入分数背包
            res += items[i].ratio * remCap;
            break;
        }
    }
    return (int)res;
}

void branchAndBound() {
    queue<Node> Q;
    Node initial;
    initial.depth = 0;
    initial.currentV = 0;
    initial.currentW = 0;
    memset(initial.isSelected, 0, sizeof(initial.isSelected));
    initial.upBound = getUpBound(initial);
    Q.push(initial);

    while (!Q.empty()) {
        Node e = Q.front();
        Q.pop();

        // 到达叶子节点，更新全局最优解
        if (e.depth == n) {
            if (e.currentV > bestV) {
                bestV = e.currentV;
                memcpy(bestX, e.isSelected, sizeof(bestX));
            }
        } else {
            // 1. 拓展左子节点：放入第 depth+1 个物品
            if (e.currentW + items[e.depth + 1].w <= c) {
                Node leftChild;
                leftChild.depth = e.depth + 1;
                leftChild.currentV = e.currentV + items[e.depth + 1].v;
                leftChild.currentW = e.currentW + items[e.depth + 1].w;
                memcpy(leftChild.isSelected, e.isSelected, sizeof(bool) * n);
                leftChild.isSelected[e.depth + 1] = true;
                leftChild.upBound = leftChild.currentV; // 确定值就是价值
                
                // 即使它是叶子节点的前一步，也将其压入，方便后续统一处理
                // 或者如果已经到n-1层，可以直接在此处更新最优解，此处为了逻辑统一继续压入
                 if (leftChild.depth == n) {
                    if (leftChild.currentV > bestV) {
                        bestV = leftChild.currentV;
                        memcpy(bestX, leftChild.isSelected, sizeof(bestX));
                    }
                } else {
                     leftChild.upBound = getUpBound(leftChild);
                    Q.push(leftChild);
                }
            }

            // 2. 拓展右子节点：不放入第 depth+1 个物品
            Node rightChild;
            rightChild.depth = e.depth + 1;
            rightChild.currentV = e.currentV;
            rightChild.currentW = e.currentW;
            memcpy(rightChild.isSelected, e.isSelected, sizeof(bool) * n);
            rightChild.isSelected[e.depth + 1] = false;
            rightChild.upBound = getUpBound(rightChild);

            // 剪枝判断：只有上界优于当前已知最优解时才入队
            if (rightChild.upBound > bestV) {
                Q.push(rightChild);
            }
        }
    }
}

int main() {
    cout << "请输入物品个数:" << endl;
    cin >> n;
    cout << "请输入背包容量:" << endl;
    cin >> c;

    for (int i = 1; i <= n; i++) {
        cin >> items[i].w >> items[i].v;
        items[i].id = i;
        items[i].ratio = (double)items[i].v / items[i].w;
    }

    // 分支限界法通常配合物品按性价比降序排列以获得紧确上界
    sort(items + 1, items + n + 1, compareItems);

    branchAndBound();

    cout << "最优价值:" << (int)bestV << endl;
    cout << "选择的物品ID(原始输入顺序):" << endl;
    // 注意：bestX是基于排序后的数组索引，输出时需映射回原ID或简单展示
    // 此处简化为打印决策向量的含义
    cout << "最终方案向量(对应排序后物品): ";
    for(int i=1; i<=n; i++) {
         cout << bestX[i] << " ";
    }
    cout << endl;

    return 0;
}

分支限界法在处理大规模数据时的效率优势通常体现在其优秀的剪枝能力上，以下是算法执行过程的示例：

总结

回溯法代码简洁，易于理解，适合教学和小规模数据的暴力穷举验证；分支限界法通过引入上界估算和队列管理，能够在庞大的解空间中迅速定位最优解，是工程实践中解决背包类问题的常用手段。开发者可根据具体的性能需求和约束条件选择合适的算法。

以上就是C++回溯与分支限界算法分别解决背包问题的详细内容，更多关于C++经典算法与优化的资料请关注本站其它相关文章！