编辑代码

import java.util.ArrayList;
import java.util.List;
class Main {
    public static void optimizeKnapsack(int capacity, List<Fruit> fruits) {
        int n = fruits.size();
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= fruits.get(i - 1).weight) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - fruits.get(i - 1).weight] + fruits.get(i - 1).value);
                }
            }
        }
        List<Fruit> selectedFruits = new ArrayList<>();
        int i = n;
        int j = capacity;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                selectedFruits.add(fruits.get(i - 1));
                j -= fruits.get(i - 1).weight;
            }
            i--;
        }
        System.out.println("装水果的策略：");
        for (int k = selectedFruits.size() - 1; k >= 0; k--) {
            Fruit fruit = selectedFruits.get(k);
            System.out.printf("%s\t重量：%dkg\t价值：%d元\n", fruit.name, fruit.weight, fruit.value);
        }
        System.out.printf("总价值：%d元\n", dp[n][capacity]);
    }
    public static void main(String[] args) {
        int capacity = 20;
        List<Fruit> fruits = new ArrayList<>();
        fruits.add(new Fruit("苹果", 15, 300));
        fruits.add(new Fruit("香蕉", 18, 180));
        fruits.add(new Fruit("橘子", 10, 150));
        fruits.add(new Fruit("猕猴桃", 9, 270));
        optimizeKnapsack(capacity, fruits);
    }
}
class Fruit {
    public String name;
    public int weight;
    public int value;
    public Fruit(String name, int weight, int value) {
        this.name = name;
        this.weight = weight;
        this.value = value;
    }
}