编辑代码

package homework;
import java.util.Arrays;

public class KnapsackProblem {

    static class Item implements Comparable<Item> {
        int weight;
        int value;
        double ratio;

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

        @Override
        public int compareTo(Item other) {
            return Double.compare(other.ratio, this.ratio);
        }
    }

    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); // 按单位价值排序

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

        while (currentIndex < n) {
            if (currentWeight + items[currentIndex].weight <= capacity) {
                currentWeight += items[currentIndex].weight;
                currentValue += items[currentIndex].value;
                currentIndex++;
            } else {
                int remainingCapacity = capacity - currentWeight;
                double remainingValue = remainingCapacity * items[currentIndex].ratio;
                currentValue += (int) remainingValue;
                break;
            }
        }

        return currentValue;
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        int maxProfit = knapsack(weights, values, capacity);
        System.out.println("Maximum Profit: " + maxProfit);
    }
}