背包问题-优先队列式分支限界法

优先队列式分支限界法是一种用于解决0/1背包问题的算法。它通过使用优先队列来选择下一个要扩展的节点，并使用上界函数来估计节点的最优解。下面是该算法的核心代码：

template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i) {
    Typew cleft = c - cw; // 剩余容量
    Typep b = cp; // 以剩余物品单位重量价值递减序装入物品
    while (i <= n && w[i] <= cleft) {
        cleft -= w[i];
        b += p[i];
        i++;
    }
    // 装满背包
    if (i <= n)
        b += p[i]/w[i] * cleft;
    return b;
}

该算法的基本思想是，首先将物品按照单位重量价值递减的顺序排列，然后从根节点开始，依次扩展子节点。在扩展节点时，根据上界函数的值进行剪枝，只扩展有可能成为最优解的节点。通过不断扩展节点并更新当前最优解，最终找到问题的最优解。