Branch Bound Method 0-1背包问题

Branch Bound Method 是一种求解优化问题的方法，其中 0-1 背包问题是这些问题中的一个经典例子。0-1 背包问题是指有一个背包和一些物品，每个物品有自己的重量和价值，背包有一个固定的容量，如何在不超过背包容量的情况下，使得背包中所装物品的总价值最大。

Branch Bound Method 的基本思路是将问题分解成一个个子问题，每个子问题都可以用一个界限值来表示，然后通过比较界限值来不断缩小搜索空间，直到得到最优解。

在 0-1 背包问题中，Branch Bound Method 的具体实现可以是：

1. 将所有物品按照单位重量的价值从大到小排序。
2. 用一个队列来存储待扩展的子问题，初始时队列中只有一个节点，即全部物品都未考虑时的背包问题。
3. 对于每个节点，计算其上界值，即当前背包容量下能够装下的最大价值，将其与当前的最优解进行比较，如果上界值小于等于当前最优解，就可以剪枝。
4. 将当前节点分为装入下一个物品和不装入下一个物品两个子问题，分别计算它们的上界值，并将它们加入队列中。
5. 重复进行步骤 3 和 4，直到队列为空。

通过 Branch Bound Method 可以在较短的时间内得到 0-1 背包问题的最优解，但是它的时间复杂度仍然是指数级别的，因此对于大规模的问题，需要使用更加高效的算法。

相关问题

01背包问题回溯法和分支限界法有什么不同

### 01背包问题中的回溯法与分支限界法区别

#### 解决策略的不同
对于01背包问题，回溯法旨在找到解空间树中满足约束条件的所有可能解。相比之下，分支限界法则专注于快速定位至少一个可行解，在某些情况下可能是最优解。这种差异源于两者不同的搜索目标设定[^4]。

#### 搜索模式对比
- **回溯法**：采用深度优先遍历策略构建解空间树。这意味着算法会尽可能深入探索每一个潜在解决方案路径直到达到叶子节点或遇到不满足条件的情况才会返回上一层继续尝试其他可能性[^2]。

- **分支限界法**：通常采取广度优先或者基于成本估计的优先级队列来进行层次化扫描。这种方法允许程序在早期阶段就能接触到多个候选方案，并通过剪枝操作排除那些不可能产生更优结果的部分子集。

#### 扩展节点处理机制
- 在回溯过程中，每当某个中间状态无法进一步发展成有效解答时就会被标记为“死结点”，随后立即退回到最近未完全展开的状态重新考虑新的前进路线；

- 对于分支限界而言，任何时刻每个活跃（即尚未完成全部后代生成）的位置仅能作为单一扩展起点来创建其直接下层元素集合；而且这些新产生的成员会被加入到等待评估的数据结构里以便后续按需选取最有潜力者推进计算流程。

#### 存储需求考量
由于上述工作原理上的差别，导致两者的内存占用特性也有所区分。具体来说，因为分支限界倾向于保存更多关于当前正在考察范围的信息，所以它往往需要更大的辅助存储资源支持整个运算周期内的数据管理活动。相反地，当面临硬件环境限制特别是可用RAM不足的情形下，利用较少额外开销即可运作良好的回溯技术或许更具优势。

def backtrack_knapsack(items, capacity):
    best_value = [0]
    
    def dfs(index, current_weight, value):
        if index >= len(items) or current_weight > capacity:
            return
        
        # 不选第index个物品
        dfs(index + 1, current_weight, value)

        # 选第index个物品
        item_weight, item_value = items[index]
        
        if (current_weight + item_weight <= capacity and 
                value + item_value > best_value[0]):
            best_value[0] = value + item_value
            
        dfs(index + 1, current_weight + item_weight, value + item_value)
            
    dfs(0, 0, 0)
    return best_value[0]

from queue import PriorityQueue

class Node(object):
    def __init__(self, level, profit, weight):
        self.level = level
        self.profit = profit
        self.weight = weight
    
    def __lt__(self, other):
        return self.profit / float(self.weight) > other.profit / float(other.weight)


def branch_and_bound_knapsack(weights, values, max_capacity):
    n = len(values)
    q = PriorityQueue()
    start_node = Node(-1, 0, 0)
    q.put(start_node)
    u = start_node
    v = start_node
    while not q.empty():
        u = q.get()

        next_level = u.level + 1
        if next_level == n:
            break 

        v = Node(next_level, u.profit, u.weight)

        # Not taking the nth item.
        q.put(v)

        w = weights[next_level]
        p = values[next_level]

        if(u.weight + w <= max_capacity):   
            child_v = Node(next_level, u.profit+p ,u.weight+w )
            if(child_v.profit > v.profit ):
               v=child_v
            q.put(child_v )

    return v.profit


items = [(2, 3), (3, 4), (4, 5), (5, 8)]  # (weight, value)
capacity = 5
print(f'Backtrack Method Result: {backtrack_knapsack(items, capacity)}')
print(f'Branch And Bound Method Result: {branch_and_bound_knapsack([i[0] for i in items], [i[1] for i in items], capacity)}')