分支限界法求解01背包pta

### 使用分支限界法解决01背包问题

#### 什么是分支限界法？

分支限界法是一种用于求解组合优化问题的方法，通过构建状态空间树来探索可能的解决方案。对于每一个节点，算法计算目标函数的一个界限，并据此决定是否继续扩展该节点。

#### 构建状态空间树

在处理01背包问题时，可以将物品逐个考虑放入或不放入背包中，从而形成二叉决策树结构。每个节点代表当前状态下已做出的选择序列以及剩余待选物品列表。根结点表示没有任何东西被选择的状态；左子树对应于把某件商品加入集合的情况；右子树则意味着放弃这件货物[^2]。

#### 设计边界条件

为了提高效率，在遍历过程中需要设置合理的剪枝策略：

- **可行性约束**：当累积重量超过容量上限时停止进一步深入；
- **最优性剪辑**：利用上界估计提前终止那些不可能带来更优解的路径搜索。

#### 计算上下界

采用动态规划的思想预估最大价值作为上界指导搜索方向。具体来说就是基于已经装载好的部分加上剩下未考察过的最佳情况下的总收益之和。这样可以在一定程度上减少不必要的穷举次数[^3]。

#### Python实现代码示例

下面是一个简单的Python程序实现了上述思路：

from queue import PriorityQueue

def knapsack_branch_and_bound(weights, values, capacity):
    n = len(weights)

    class Node:
        def __init__(self, level=0, profit=0, weight=0, bound=None):
            self.level = level
            self.profit = profit
            self.weight = weight
            self.bound = bound
        
        def __lt__(self, other):
            return self.bound > other.bound
    
    def calculate_bound(node):
        if node.weight >= capacity:
            return 0
        else:
            result = node.profit
            j = node.level + 1
            totweight = node.weight
            
            while (j < n and totweight + weights[j] <= capacity):
                totweight += weights[j]
                result += values[j]
                j += 1
                
            k = j
            if k < n:
                result += (capacity - totweight) * float(values[k]) / weights[k]

            return result

    q = PriorityQueue()
    
    v = Node(0, 0, 0)
    max_profit = 0
    v.bound = calculate_bound(v)
    q.put((v.bound, v))
    
    while not q.empty():
        _, u = q.get()

        if u.bound > max_profit:
            v = Node(u.level + 1, u.profit + values[u.level], u.weight + weights[u.level])
            
            if v.weight <= capacity and v.profit > max_profit:
                max_profit = v.profit
                
            v.bound = calculate_bound(v)
            if v.bound > max_profit:
                q.put((v.bound, v))

            w = Node(level=u.level + 1, profit=u.profit, weight=u.weight)
            w.bound = calculate_bound(w)
                
            if w.bound > max_profit:
                q.put((w.bound, w))
                    
    return max_profit


weights = [2, 5, 10, 5]
values = [40, 30, 50, 10]
capacity = 16
print(f"The maximum value that can be obtained is {knapsack_branch_and_bound(weights, values, capacity)}")