探索最优解的利器（Java语言分支限界算法入门教程）

核心思想三要素

1. 分支（Branching）：将当前问题分解为若干子问题。
2. 限界（Bounding）：计算每个子问题的上下界，用于判断是否值得继续探索。
3. 剪枝（Pruning）：若某子问题的界已劣于当前最优解，则直接舍弃。

实战：用Java实现0-1背包问题的分支限界解法

我们以经典的0-1背包问题为例：给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求不超过容量的前提下能装入的最大价值。

步骤说明：

• 按单位价值（v[i]/w[i]）对物品降序排序，便于估算上界。
• 定义一个“节点”类，包含当前重量、当前价值、上界估计值、当前考虑的物品索引。
• 使用优先队列（最大堆，按上界排序），每次取出上界最大的节点进行扩展。
• 对每个节点，尝试放入或不放入下一个物品，更新状态并计算新上界。
• 若某节点的上界小于等于当前已知最优解，则剪枝。

Java代码实现：

import java.util.*;// 节点类class Node {    int level;      // 当前考虑第几个物品（从0开始）    int profit;     // 当前总价值    int weight;     // 当前总重量    double bound;   // 上界估计值    public Node(int level, int profit, int weight) {        this.level = level;        this.profit = profit;        this.weight = weight;        this.bound = 0;    }}// 物品类class Item {    int weight;    int value;    double ratio;    public Item(int w, int v) {        this.weight = w;        this.value = v;        this.ratio = (double) v / w;    }}public class BranchAndBoundKnapsack {    // 计算上界    public static double getBound(Node u, int n, Item[] items, int capacity) {        if (u.weight >= capacity) return 0;        double bound = u.profit;        int j = u.level + 1;        int totalWeight = u.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].ratio;        }        return bound;    }    public static int knapsack(int capacity, Item[] items) {        int n = items.length;        // 按单位价值降序排序        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));        PriorityQueue pq = new PriorityQueue<>((a, b) -> Double.compare(b.bound, a.bound));        Node root = new Node(-1, 0, 0);        root.bound = getBound(root, n, items, capacity);        pq.offer(root);        int maxValue = 0;        while (!pq.isEmpty()) {            Node current = pq.poll();            // 如果上界小于当前最优解，剪枝            if (current.bound <= maxValue) continue;            // 到达叶子节点            if (current.level == n - 1) continue;            // 尝试放入下一个物品            int nextLevel = current.level + 1;            Item nextItem = items[nextLevel];            // 分支1：放入物品            if (current.weight + nextItem.weight <= capacity) {                Node include = new Node(nextLevel,                        current.profit + nextItem.value,                        current.weight + nextItem.weight);                if (include.profit > maxValue) {                    maxValue = include.profit;                }                include.bound = getBound(include, n, items, capacity);                if (include.bound > maxValue) {                    pq.offer(include);                }            }            // 分支2：不放入物品            Node exclude = new Node(nextLevel, current.profit, current.weight);            exclude.bound = getBound(exclude, n, items, capacity);            if (exclude.bound > maxValue) {                pq.offer(exclude);            }        }        return maxValue;    }    public static void main(String[] args) {        Item[] items = {            new Item(10, 60),            new Item(20, 100),            new Item(30, 120)        };        int capacity = 50;        int result = knapsack(capacity, items);        System.out.println("最大价值为: " + result); // 输出：220    }}

为什么选择分支限界？

相比暴力枚举（时间复杂度O(2^n)），分支限界通过剪枝有效减少搜索节点；相比动态规划，它不需要存储整个状态表，在某些大规模问题中内存更友好。当然，其效率高度依赖于上界估计的质量——越紧的上界，剪枝效果越好。

小结

本教程详细讲解了分支限界算法的基本原理，并通过Java代码完整实现了0-1背包问题的求解。无论你是算法初学者还是希望巩固知识的开发者，掌握这一方法都能显著提升你解决组合优化问题的能力。

记住：算法的核心在于理解思想，而非死记代码。多动手实践，尝试将其应用到其他问题（如任务调度、路径规划），你将收获更多！

SEO关键词提示：本教程涵盖 分支限界算法、Java实现、算法教程 和 回溯与剪枝 等核心概念，适合搜索引擎优化学习。