编辑代码

import java.util.ArrayList;
import java.util.List;

public class KnapsackProblem {
    static class Fruit {
        String name;
        int weight;
        int value;

        public Fruit(String name, int weight, int value) {
            this.name = name;
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Fruit[] fruits = {
                new Fruit("苹果", 15, 300),
                new Fruit("香蕉", 18, 180),
                new Fruit("橘子", 10, 150),
                new Fruit("猕猴桃", 9, 270)
        };

        int capacity = 20;
        int n = fruits.length;

        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (fruits[i - 1].weight <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - fruits[i - 1].weight] + fruits[i - 1].value);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        int maxValue = dp[n][capacity];
        System.out.println("装水果的最大价值为：" + maxValue);

        List<String> strategy = new ArrayList<>();
        int w = capacity;
        for (int i = n; i > 0 && maxValue > 0; i--) {
            if (maxValue != dp[i - 1][w]) {
                strategy.add(fruits[i - 1].name);
                maxValue -= fruits[i - 1].value;
                w -= fruits[i - 1].weight;
            }
        }

        System.out.println("装水果的策略：");
        for (int i = strategy.size() - 1; i >= 0; i--) {
            System.out.println(strategy.get(i));
        }
    }
}