5.4.3 经典分支限界问题

1. 0-1背包问题（分支限界解法）

问题描述：

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。每件物品只能选择放入或不放入背包（即0-1决策），求解将哪些物品装入背包可使价值总和最大。

生活例子：

想象你是一名登山者，准备一次重要的登山活动。你有一个容量有限的背包，以及多种可能带走的装备（食物、水、帐篷、睡袋等）。每种装备都有自己的重量和对登山活动的价值（实用性）。你需要决定带哪些装备，使得在不超过背包容量的情况下，总价值最大。

分支限界法思路：

与回溯法不同，分支限界法使用优先队列来管理搜索空间，优先探索最有希望的分支。对于0-1背包问题：

1. 将物品按单位价值（价值/重量）降序排序
2. 使用优先队列存储待探索的节点，按上界排序
3. 对于每个节点，考虑两种选择：选择当前物品或不选择当前物品
4. 使用上界函数剪枝，如果节点的上界小于当前已知的最大价值，则不再探索该节点

上界计算方法：

上界是对最优解的估计，通常是一个比实际最优解更乐观的值。对于0-1背包问题，上界计算方法为：

1. 已选物品的总价值
2. 加上剩余容量可以容纳的未考虑物品的价值（按单位价值排序后贪心选择）
3. 对于最后一个不能完全放入的物品，按比例计算其价值

图解过程：

假设有3件物品：

• 物品1：重量=10，价值=60，单位价值=6
• 物品2：重量=20，价值=100，单位价值=5
• 物品3：重量=30，价值=120，单位价值=4

背包容量为50。

按单位价值排序后：物品1 > 物品2 > 物品3

                        根节点(level=-1, profit=0, weight=0)
                       /                                  \
           不选物品1                                       选物品1
(level=0, profit=0, weight=0)                 (level=0, profit=60, weight=10)
       /            \                                 /            \
 不选物品2          选物品2                      不选物品2          选物品2
  ...                ...                          ...        (level=1, profit=160, weight=30)
                                                              /            \
                                                        不选物品3          选物品3
                                                          ...       (level=2, profit=280, weight=60)
                                                                    超出容量，不可行

代码实现：

public static int knapsackBranchAndBound(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    
    // 计算单位价值并按降序排序
    Item[] items = new Item[n];
    for (int i = 0; i < n; i++) {
        items[i] = new Item(i, weights[i], values[i]);
    }
    // 按单位价值（价值/重量）降序排序
    Arrays.sort(items, (a, b) -> Double.compare(b.valuePerWeight, a.valuePerWeight));
    
    // 使用优先队列，按上界降序排序（优先探索上界高的节点）
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Double.compare(b.bound, a.bound));
    
    // 创建根节点
    Node root = new Node();
    root.level = -1;      // 表示还未考虑任何物品
    root.profit = 0;      // 当前价值为0
    root.weight = 0;      // 当前重量为0
    root.bound = getBound(root, items, capacity, n);  // 计算上界
    
    pq.add(root);  // 将根节点加入优先队列
    
    int maxProfit = 0;  // 当前找到的最大价值
    
    // 当优先队列非空时，继续搜索
    while (!pq.isEmpty()) {
        // 取出队首节点（上界最大的节点）
        Node node = pq.poll();
        
        // 剪枝：如果上界小于等于当前最大价值，则跳过
        if (node.bound <= maxProfit) continue;
        
        // 移动到下一个物品
        node.level++;
        
        // 如果已经考虑完所有物品，则跳过
        if (node.level == n) continue;
        
        // 情况1：不选择当前物品
        Node skipNode = new Node();
        skipNode.level = node.level;  // 当前考虑的物品索引
        skipNode.weight = node.weight;  // 保持重量不变
        skipNode.profit = node.profit;  // 保持价值不变
        skipNode.bound = getBound(skipNode, items, capacity, n);  // 重新计算上界
        
        // 如果上界大于当前最大价值，则加入队列继续探索
        if (skipNode.bound > maxProfit) {
            pq.add(skipNode);
        }
        
        // 情况2：选择当前物品（如果容量允许）
        if (node.weight + items[node.level].weight <= capacity) {
            Node takeNode = new Node();
            takeNode.level = node.level;  // 当前考虑的物品索引
            takeNode.weight = node.weight + items[node.level].weight;  // 增加重量
            takeNode.profit = node.profit + items[node.level].value;  // 增加价值
            takeNode.bound = getBound(takeNode, items, capacity, n);  // 重新计算上界
            
            // 更新当前找到的最大价值
            maxProfit = Math.max(maxProfit, takeNode.profit);
            
            // 如果上界大于当前最大价值，则加入队列继续探索
            if (takeNode.bound > maxProfit) {
                pq.add(takeNode);
            }
        }
    }
    
    return maxProfit;
}

// 计算节点的上界
private static double getBound(Node node, Item[] items, int capacity, int n) {
    // 如果已经超过容量，则上界为0（不可行解）
    if (node.weight > capacity) return 0;
    
    // 上界初始值为当前已选物品的总价值
    double bound = node.profit;
    int j = node.level + 1;  // 从下一个物品开始考虑
    int totalWeight = node.weight;  // 当前总重量
    
    // 贪心策略：尽可能多地装入物品（按单位价值排序后）
    while (j < n && totalWeight + items[j].weight <= capacity) {
        totalWeight += items[j].weight;
        bound += items[j].value;
        j++;
    }
    
    // 如果还有剩余容量，装入部分物品（按比例）
    if (j < n) {
        bound += (capacity - totalWeight) * items[j].valuePerWeight;
    }
    
    return bound;
}

// 物品类
static class Item {
    int id;       // 物品编号
    int weight;   // 物品重量
    int value;    // 物品价值
    double valuePerWeight;  // 单位价值（价值/重量）
    
    public Item(int id, int weight, int value) {
        this.id = id;
        this.weight = weight;
        this.value = value;
        this.valuePerWeight = (double) value / weight;
    }
}

// 搜索树节点类
static class Node {
    int level;   // 当前考虑的物品索引
    int profit;  // 当前已选物品的总价值
    int weight;  // 当前已选物品的总重量
    double bound;  // 上界（对最优解的估计）
}

时间复杂度分析：

最坏情况下，分支限界法需要探索所有可能的组合，时间复杂度为O(2^n)。但在实际应用中，由于有效的剪枝策略，通常可以大大减少搜索空间。

空间复杂度分析：

O(n)，主要用于存储优先队列中的节点。

与动态规划解法的比较：

应用场景：

• 资源分配问题
• 投资组合优化
• 项目选择问题
• 装载问题