优先队列分支限界法求解01背包

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

#### 算法概述
分支限界法是一种通过构建部分解空间树来寻找最优解的方法。对于01背包问题，该方法利用优先队列为节点分配优先级并选择最有希望的部分解继续扩展。为了提高效率，在遍历过程中会计算当前路径的价值上限作为剪枝条件[^1]。

#### 关键概念解释
- **活结点**：尚未被完全处理的子集。
- **死结点**：已经完成探索或不可能产生更优解的子集。
- **上界估计函数**：用来预测如果沿着这条路线走下去可能获得的最大价值，以此决定是否值得进一步考察此路线下方的其他可能性[^2]。

#### 实现思路
采用广度优先策略配合最大堆（即大根堆），每次从未访问过的节点中挑选具有最高预期效益者先行深入研究；当遇到新的可行方案时，则将其加入待查列表等待后续评估。与此同时，保持记录迄今为止发现的最佳整数规划解答及其对应总重量与物品集合。

#### C语言代码示例
下面给出一段基于上述原理编写的C程序：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int weight;
    double value;
} Item;

// 定义一个结构体表示每个状态 (剩余容量, 当前价值, 已选物品索引)
typedef struct State {
    int capacity;
    double profit;
    int level; // 物品编号
} State;

void swap(State* a, State* b) {
    State t = *a;
    *a = *b;
    *b = t;
}

double bound(int n, const Item items[], State state) {
    if(state.capacity <= 0){
        return 0;
    }
    
    int j=state.level+1,k=n-1;
    double totalWeight=state.capacity,totalValue=state.profit;
  
    while(j<=k && items[j].weight<=totalWeight){ 
        totalWeight-=items[j++].weight;
        totalValue+=items[j-1].value;
    }

    if(j<=k){
        totalValue+=(totalWeight/items[j].weight)*items[j].value;
    } 

    return totalValue;
}

int cmp(const void*a,const void*b){
    return ((Item*)b)->value - ((Item*)a)->value;
}

void knapsack(int n, Item items[], int W, double &maxProfit,int bestSet[]){
    qsort(items,n,sizeof(Item),cmp);
    maxProfit = 0.0;
    State queue[n];
    int front=-1,rear=-1;
    State u,v;
    v.capacity=W;
    v.profit=0.0;
    v.level=-1;
    rear++;
    queue[rear]=v;

    while(front!=rear){
        v=queue[++front];

        u=v;
        ++u.level;
        
        if(u.level>=n){
            continue;
        }

        if((u.capacity-items[u.level].weight)>=0){
            u.capacity -= items[u.level].weight;
            u.profit += items[u.level].value;
            
            if(u.profit>maxProfit){
                maxProfit=u.profit;
                
                for(int i=0;i<u.level;++i){
                    bestSet[i]=(bestSet[i]|(u.capacity<items[i].weight));
                }
                bestSet[u.level]=1;
            }
            
            double tempBound=bound(n,items,u);

            if(tempBound>maxProfit){
                rear++;
                queue[rear]=u;
            }
        }

        u=v;
        ++u.level;
        if(bound(n,items,u)>maxProfit){
            rear++;
            queue[rear]=u;
        }
    }
}

这段代码实现了使用优先队列和分支限界法求解01背包问题的功能。其中`knapsack()` 函数接收参数 `n`, 表示有几件商品可供选择；数组 `items[]` 存储每一件商品的信息；以及背包所能承受的最大载重 `W`. 输出结果保存于全局变量 `maxProfit` 和 `bestSet[]`.