分支限界法求解0/1背包问题

0/1背包问题是一个经典的组合优化问题，它的目标是在给定的一组物品中选择尽可能多的物品放入一个容量为C的背包中，使得这些物品的总重量不超过C，同时总价值最大。

分支限界法是一种常用的求解0/1背包问题的方法。其基本思想是将问题分解成若干个子问题，并对每个子问题进行求解，直到找到最优解为止。

以下是分支限界法求解0/1背包问题的步骤：

1. 定义节点数据结构。每个节点包括以下属性：当前已选物品的重量、当前已选物品的价值、当前已选物品的数量、剩余可选物品的集合。

2. 定义优先级队列。用于存储待扩展的节点，按照节点价值的上界（即当前已选物品的总价值加上剩余可选物品的价值上界）从大到小排序。

3. 初始化根节点。将根节点的属性设置为：当前已选物品的重量、价值和数量均为0，剩余可选物品的集合为所有物品。

4. 进入循环。如果优先级队列不为空，则取出队首节点进行扩展。对于每个节点，分别考虑选择下一个物品和不选择下一个物品两种情况，生成两个子节点，并计算它们的上界。如果子节点表示的问题仍然有解，则将它们加入优先级队列中。

5. 判断是否找到最优解。如果当前已选物品的价值加上剩余可选物品的价值上界小于已知的最优解，则说明当前节点不可能得到更优的解，直接舍弃。

6. 返回最优解。当优先级队列为空时，说明已经遍历完所有节点，返回最优解。

分支限界法是一种非常高效的求解0/1背包问题的方法，时间复杂度为O(2^n)，其中n为物品数量。它可以用于求解大规模的组合优化问题，例如旅行商问题、集合覆盖问题等。