01背包问题分支限界java代码

下面是一个基于分支限界算法的01背包问题的Java代码，代码注释中有详细解释：

import java.util.*;

public class KnapsackProblem {
    // 物品类，包含重量和价值两个属性
    public static class Item {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    // 节点类，包含父节点、当前物品、当前重量、当前价值三个属性
    public static class Node {
        Node parent;
        int itemIndex;
        int weight;
        int value;

        public Node(Node parent, int itemIndex, int weight, int value) {
            this.parent = parent;
            this.itemIndex = itemIndex;
            this.weight = weight;
            this.value = value;
        }
    }

    /**
     * 基于分支限界算法的01背包问题求解
     * @param items 物品列表
     * @param capacity 背包容量
     * @return 能够获得的最大价值
     */
    public static int knapsack(Item[] items, int capacity) {
        // 将物品按单位价值（value/weight）从高到低排序
        Arrays.sort(items, (i1, i2) -> i2.value * i1.weight - i1.value * i2.weight);

        // 初始化队列，将根节点加入队列
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(null, -1, 0, 0));

        // 循环处理队列中的节点
        int max = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.itemIndex == items.length - 1) {
                // 当前节点为叶子节点，更新最大值
                max = Math.max(max, node.value);
            } else {
                // 当前节点不是叶子节点，分别处理选择当前物品和不选择当前物品两种情况
                int nextIndex = node.itemIndex + 1;
                int nextWeight = node.weight + items[nextIndex].weight;
                int nextValue = node.value + items[nextIndex].value;
                if (nextWeight <= capacity) {
                    // 如果选择当前物品可以放入背包，则将选择当前物品的节点加入队列
                    queue.offer(new Node(node, nextIndex, nextWeight, nextValue));
                }

                int bound = bound(items, capacity, nextWeight, nextValue, nextIndex);
                if (bound > max) {
                    // 如果不选择当前物品可以获得更大的价值，将不选择当前物品的节点加入队列
                    queue.offer(new Node(node, nextIndex, node.weight, node.value));
                }
            }
        }

        return max;
    }

    /**
     * 计算当前节点的上界
     * @param items 物品列表
     * @param capacity 背包容量
     * @param weight 当前重量
     * @param value 当前价值
     * @param index 当前物品下标
     * @return 上界
     */
    private static int bound(Item[] items, int capacity, int weight, int value, int index) {
        if (weight >= capacity) {
            // 如果当前重量已经超过背包容量，返回0
            return 0;
        }

        int bound = value;
        int remaining = capacity - weight;
        while (index < items.length && items[index].weight <= remaining) {
            // 将剩余容量尽可能地装满
            bound += items[index].value;
            remaining -= items[index].weight;
            index++;
        }
        if (index < items.length) {
            // 装满剩余容量后，将当前物品按照单位价值装入背包
            bound += remaining * items[index].value / items[index].weight;
        }

        return bound;
    }

    public static void main(String[] args) {
        // 测试用例
        Item[] items = new Item[] {
                new Item(2, 3),
                new Item(3, 4),
                new Item(4, 5),
                new Item(5, 6)
        };
        int capacity = 8;
        System.out.println(knapsack(items, capacity)); // 输出10
    }
}