编辑代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class BranchAndBoundKnapsack {

    static class Item {
        int weight;
        int value;
        double valuePerWeight;

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

    static class Node {
        int level; // 当前节点的层级
        int weight; // 当前节点的总重量
        int value; // 当前节点的总价值
        List<Item> selectedItems; // 当前节点选择的物品

        public Node(int level, int weight, int value, List<Item> selectedItems) {
            this.level = level;
            this.weight = weight;
            this.value = value;
            this.selectedItems = selectedItems;
        }
    }

    public static int knapsack(Item[] items, int capacity) {
        // 按价值/重量降序排序
        Arrays.sort(items, Comparator.comparingDouble(item -> -item.valuePerWeight));

        // 初始化根节点
        Node root = new Node(0, 0, 0, new ArrayList<>());
        // 初始化边界值
        int bestValue = 0;

        // 使用优先队列存储节点，优先级按价值降序排列
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> -node.value));
        queue.offer(root);

        // 循环遍历队列，直到队列为空
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            // 如果当前节点的重量超过背包容量，则跳过
            if (node.weight > capacity) {
                continue;
            }

            // 更新最佳价值
            bestValue = Math.max(bestValue, node.value);

            // 如果当前节点是叶子节点，则不再继续扩展
            if (node.level == items.length) {
                continue;
            }

            // 扩展当前节点
            // 选择当前物品
            Item item = items[node.level];
            List<Item> selectedItems = new ArrayList<>(node.selectedItems);
            selectedItems.add(item);
            Node leftChild = new Node(
                    node.level + 1,
                    node.weight + item.weight,
                    node.value + item.value,
                    selectedItems
            );
            queue.offer(leftChild);

            // 不选择当前物品
            Node rightChild = new Node(node.level + 1, node.weight, node.value, node.selectedItems);
            queue.offer(rightChild);
        }

        return bestValue;
    }

    public static void main(String[] args) {
        // 物品信息
        Item[] items = {
                new Item(10, 60),
                new Item(20, 100),
                new Item(30, 120)
        };
        // 背包容量
        int capacity = 50;

        // 计算最大价值
        int maxValue = knapsack(items, capacity);
        System.out.println("最大价值为：" + maxValue); // 输出：最大价值为：220
    }
}