使用分支界限法实现0-1背包问题

0-1背包问题是指给定一个背包容量和一组物品，每个物品有对应的价值和重量，要求从中选择一些物品放入背包中，使得背包中物品的总重量不超过背包容量，且背包中物品的总价值最大化。

分支界限法是一种求解0-1背包问题的有效算法。其基本思想是将问题分解成一系列子问题，通过对子问题的求解逐步扩展搜索空间，直到找到最优解或确定最优解不存在。具体实现过程如下：

1. 将所有物品按照单位价值（即价值与重量之比）从大到小排序。

2. 初始化当前可行解为0，当前最优解为0。

3. 对于每个物品，计算将其放入背包和不放入背包两种情况下的上界。上界的计算公式为：当前可行解 + 剩余物品的单位价值之和。如果上界小于当前最优解，则剪枝。

4. 将物品按照上界从大到小排序，选取上界最大的一个物品进行扩展。如果该物品放入背包后仍然能够保持可行性，则更新当前可行解和当前最优解；否则剪枝。

5. 重复步骤4，直到搜索完所有的物品或已经找到最优解。

下面是使用Python实现分支界限法求解0-1背包问题的代码：

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.unit_value = value / weight

def knapsack(items, capacity):
    # 按照单位价值从大到小排序
    items.sort(key=lambda x: x.unit_value, reverse=True)
    
    n = len(items)
    best_value = 0
    cur_weight = 0
    cur_value = 0
    
    # 初始化搜索队列
    queue = [(0, cur_weight, cur_value)]
    
    # 开始搜索
    while queue:
        # 取出队列中的下一个结点
        i, w, v = queue.pop(0)
        
        # 计算上界
        upper_bound = v + (capacity - w) * items[i].unit_value
        
        # 如果上界小于当前最优解，剪枝
        if upper_bound <= best_value:
            continue
        
        # 如果该结点是叶子结点，更新当前最优解
        if i == n:
            best_value = max(best_value, v)
            continue
        
        # 扩展左子树（不放入背包）
        queue.append((i+1, w, v))
        
        # 扩展右子树（放入背包）
        if w + items[i].weight <= capacity:
            queue.append((i+1, w+items[i].weight, v+items[i].value))
    
    return best_value

该算法的时间复杂度为O(2^n)，其中n为物品的个数。在实际应用中，可以通过启发式规则或者剪枝策略来提高算法的效率。