Java实现0-1背包问题（分支限界法详解教程）

什么是分支限界法？

分支限界法（Branch and Bound）是一种用于求解组合优化问题的算法策略。它通过系统地枚举所有可能的解空间（分支），并利用上界或下界（限界）剪枝掉不可能产生最优解的子树，从而提高效率。

在0-1背包问题中，我们通常使用优先队列式分支限界法，每次扩展当前最有希望的节点（即当前价值 + 上界估计最大的节点）。

算法思路

1. 对物品按单位价值（价值/重量）降序排序，便于计算上界。
2. 定义一个状态节点类 Node，包含当前层级、当前重量、当前价值、上界等信息。
3. 使用优先队列（最大堆）存储待扩展的节点，优先级由上界决定。
4. 从根节点开始，依次生成左子节点（选择当前物品）和右子节点（不选当前物品）。
5. 若某节点的上界小于当前已知最优解，则剪枝。
6. 当遍历完所有可能路径后，返回最大价值。

Java代码实现

以下是完整的 Java 实现：

import java.util.*;class Item {    int weight;    int value;    double ratio;    Item(int w, int v) {        weight = w;        value = v;        ratio = (double) v / w;    }}class Node {    int level;       // 当前考虑第几个物品（从0开始）    int weight;      // 当前总重量    int profit;      // 当前总价值    double bound;    // 上界估计值    Node(int l, int w, int p) {        level = l;        weight = w;        profit = p;    }}public class KnapsackBranchBound {    // 计算上界    static double getBound(Node node, int capacity, Item[] items) {        if (node.weight >= capacity) {            return 0;        }        double bound = node.profit;        int totalWeight = node.weight;        int i = node.level + 1;        // 贪心地加入剩余物品（可部分加入，用于上界估计）        while (i < items.length && totalWeight + items[i].weight <= capacity) {            totalWeight += items[i].weight;            bound += items[i].value;            i++;        }        // 如果还有空间，加入下一个物品的一部分        if (i < items.length) {            bound += (capacity - totalWeight) * items[i].ratio;        }        return bound;    }    static int knapsack(int capacity, Item[] items) {        // 按单位价值降序排序        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));        PriorityQueue<Node> pq = new PriorityQueue<>(            (a, b) -> Double.compare(b.bound, a.bound)        );        Node root = new Node(-1, 0, 0);        root.bound = getBound(root, capacity, items);        pq.offer(root);        int maxProfit = 0;        while (!pq.isEmpty()) {            Node current = pq.poll();            // 若上界不大于当前最优解，剪枝            if (current.bound <= maxProfit) {                continue;            }            // 到达叶子节点            if (current.level == items.length - 1) {                continue;            }            // 左子节点：选择下一个物品            Node left = new Node(                current.level + 1,                current.weight + items[current.level + 1].weight,                current.profit + items[current.level + 1].value            );            if (left.weight <= capacity && left.profit > maxProfit) {                maxProfit = left.profit;            }            left.bound = getBound(left, capacity, items);            if (left.bound > maxProfit) {                pq.offer(left);            }            // 右子节点：不选下一个物品            Node right = new Node(                current.level + 1,                current.weight,                current.profit            );            right.bound = getBound(right, capacity, items);            if (right.bound > maxProfit) {                pq.offer(right);            }        }        return maxProfit;    }    public static void main(String[] args) {        int capacity = 50;        Item[] items = {            new Item(10, 60),            new Item(20, 100),            new Item(30, 120)        };        System.out.println("最大价值为: " + knapsack(capacity, items));        // 输出: 最大价值为: 220    }}

代码说明

• Item 类存储每个物品的重量、价值和单位价值比。
• Node 类表示搜索树中的一个状态节点。
• getBound 方法使用贪心策略估算当前节点能获得的最大价值（上界）。
• 主函数中对物品排序后，使用优先队列进行分支限界搜索。

总结

通过本教程，你已经掌握了如何用 Java 0-1背包问题 的 分支限界法 实现。这种方法相比暴力搜索效率更高，尤其适用于中等规模的问题实例。希望这篇 背包算法教程 能帮助你理解算法思想并提升 Java算法实现 能力！

—— 学会算法，从理解经典问题开始 ——