分支限界法

01背包问题：

分支是使用广度优先策略，依次生成扩展结点的所有分支。

分支限界法首先生成当前扩展结点的所有分支，然后再从所有活结点中选择一个作为扩展结点。每一个活结点都要计算限界（是否超出背包剩余重量），根据限界情况判断是否剪枝，或选择最有利的结点。
分支限界法有两种不同的搜索空间树方式，分别为广度优先和最小耗费优先，它们对应两种不同的方法：

队列式分支限界法(FIFO)
常规的广度优先策略。按照先进先出的原则选取下一个扩展结点，以队列储存活结点。
优先队列式分支限界法/最小耗费优先分支限界法(LC)（选择队列中背包价值最大的结点弹出并将其分支结点入队）
按照优先队列中指定的优先级，选取优先级最高的结点作为下一个扩展结点，以优先队列储存。

从根结点出发，根结点的价值为所有物品价值之和，重量为背包总重量，

每下一层背包价值会由于放不下物品重量不变，价值减少；放得下则重量减少，价值不变。

当遇到重量大于背包重量的结点，则放弃该结点；

当首先到达的叶子结点，即为背包的最优价值，因为叶子结点以上的结点想要继续往下，价值必然减少。