编辑代码

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

public class KnapsackBranchAndBound {
    private static class Item {
        int weight;
        int value;
        double unitValue;

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

    public static int knapsack(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(weights[i], values[i]);
        }

        Arrays.sort(items, Comparator.comparingDouble(i -> -i.unitValue));

        PriorityQueue<Item> pq = new PriorityQueue<>(Comparator.comparingDouble(i -> -i.unitValue));

        int currentWeight = 0;
        int currentValue = 0;
        int currentIndex = 0;

        while (currentIndex < n || !pq.isEmpty()) {
            if (currentIndex < n) {
                Item currentItem = items[currentIndex];

                if (currentWeight + currentItem.weight <= capacity) {
                    currentWeight += currentItem.weight;
                    currentValue += currentItem.value;
                    pq.offer(currentItem);
                } else {
                    double remainingCapacity = capacity - currentWeight;
                    currentValue += (remainingCapacity / currentItem.weight) * currentItem.value;
                    break;
                }

                currentIndex++;
            } else {
                Item item = pq.poll();
                currentWeight -= item.weight;
                currentValue -= item.value;
            }
        }

        return currentValue;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;

        int result = knapsack(weights, values, capacity);
        System.out.println("（20052159何思洁）最大价值：" + result);
    }
}