01背包问题分支限界算法c++

### 关于0-1背包问题的分支限界法C++实现

#### 代码示例与解释

以下是基于分支限界法求解0-1背包问题的一个简单C++程序：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node {
    int level;      // 当前节点所在的层数
    double profit;  // 到达该节点时已获得的价值总和
    double weight;  // 已放入背包中的物品重量之和
    double bound;   // 上界估计值
    
    bool operator<(const Node& other) const { return bound < other.bound; }
};

class KnapsackProblem {
public:
    void solve(int capacity, vector<int> weights, vector<int> values);

private:
    double computeBound(Node node, int n, int W);
    
    priority_queue<Node> pq;
    int maxProfit = 0;
};

double KnapsackProblem::computeBound(Node node, int n, int W) {
    if (node.weight >= W)
        return 0;
        
    int j = node.level + 1;
    double totalWeight = node.weight;
    double result = node.profit;
    
    while ((j < n) && (totalWeight + weights[j] <= W)) {
        totalWeight += weights[j];
        result += values[j];
        ++j;
    }

    if (j < n) {
        result += (W - totalWeight) * static_cast<double>(values[j]) / weights[j];
    }
    
    return result;
}

void KnapsackProblem::solve(int capacity, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    Node root{0, 0, 0};
    root.bound = computeBound(root, n, capacity);
    pq.push(root);
    
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();

        if (u.level == n || u.bound <= maxProfit) continue;

        Node v = u;
        v.level++;
        v.weight = u.weight + weights[v.level]; 
        v.profit = u.profit + values[v.level];

        if (v.weight <= capacity && v.profit > maxProfit){
            maxProfit = v.profit;
        } 

        v.bound = computeBound(v, n, capacity);  
        if (v.bound > maxProfit) pq.push(v);

        v = u;
        v.level++;   
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = computeBound(v, n, capacity);
        if (v.bound > maxProfit) pq.push(v);
    }
}

此段代码定义了一个`KnapsackProblem`类来处理具体的逻辑[^1]。其中包含了两个主要成员函数：一个是用于计算上界的辅助方法`computeBound()`，另一个则是核心解决问题的方法`solve()`. `Node`结构体用来表示树形搜索空间里的每一个结点。

在`solve()`中初始化根节点并将其加入优先队列之后进入循环直到队列为空为止，在每次迭代过程中取出具有最高预期收益(`bound`)的那个未探索过的子集作为当前考察对象[u], 接着创建它的孩子节点[v](即考虑下一个项目是否应该被选入), 并更新相应的属性(比如累积价值、剩余可用载重以及重新评估新的边界). 如果发现某个可行方案优于之前记录的最大利润，则立即刷新全局最优解[maxProfit].

最后通过比较新产生的候选解与其父辈所继承下来的预估值之间的大小关系决定是否值得进一步深入研究下去.