01背包队列分支限界法

### 01背包问题使用队列和分支限界法

#### 解决方案概述

对于01背包问题，采用优先队列式的分支限界法能够有效地找到最优解。此方法通过构建一棵决策树来进行广度优先搜索，在每一步都利用上界函数评估节点潜力并决定是否继续探索该路径[^1]。

#### 上界估计

为了优化搜索过程，需要设计有效的上界估计机制。一种简单的方式是在理想情况下假定剩余空间完全由当前最高性价比的商品填充，从而快速估算可能的最大收益值作为候选解决方案的价值上限[^3]。

#### 数据结构选择

在此过程中，通常会选择最大堆形式的优先级队列存储待处理的状态节点。每个状态表示一次特定的选择组合及其累积效益；而这些状态按照其潜在价值降序排列等待进一步考察[^4]。

#### C++实现示例

下面给出基于上述原理的具体编码实例：

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int level;       // 当前层数(即考虑到了第几个物品)
    double profit;   // 已获得利润
    double weight;   // 背包已装载重量
    double bound;    // 边界值, 即这个结点所能达到的最大价值
    
    bool operator<(const Node& rhs)const{
        return this->bound<rhs.bound;
    }
};

// 计算边界值
double Bound(Node node,int n,double capacity,pair<int,int> items[]){
    if(node.weight>=capacity){
        return 0;
    }else{
        double result=node.profit;
        int j=node.level+1;
        int totweight=node.weight;
        
        while(j<n && totweight+items[j].second<=capacity){
            totweight+=items[j].second;
            result+=items[j].first;
            j++;
        }

        if (j < n) {
            result += (capacity-totweight)*((double)(items[j].first)/items[j].second);
        }
        return result;
    }
}

void knapsack(int n,double capacity,pair<int,int> items[],int &maxprofit){
    
    priority_queue<Node> Q;
    Node u,v;
    v={-1,0,0,Bound(v,n,capacity,items)};
    maxprofit=0;
    Q.push(v);

    while(!Q.empty()){
        v=Q.top();
        Q.pop();

        if(v.level==n-1){continue;}
        
        u.level=v.level+1;
        u.weight=v.weight+items[u.level].second;
        u.profit=v.profit+items[u.level].first;

        if(u.weight<=capacity&&u.profit>maxprofit){
            maxprofit=u.profit;
        }

        u.bound=Bound(u,n,capacity,items);  
        if(u.bound>maxprofit){
            Q.push(u);
        }

        u.weight=v.weight;
        u.profit=v.profit;
        u.bound=Bound(u,n,capacity,items);
        if(u.bound>maxprofit){
            Q.push(u);
        }
    }
}