编辑代码

public class test3 {
    public static void main(String[] args) {
        // 定义水果的信息
        String[] fruits = {"苹果", "香蕉", "橘子", "猕猴桃"};
        int[] weights = {15, 18, 10, 9};  // 每种水果的重量
        int[] values = {300, 180, 150, 270};  // 每种水果的价值
        int capacity = 20;  // 背包的承重

        // 创建二维数组，用于存储中间状态的最大总价值
        int[][] dp = new int[fruits.length + 1][capacity + 1];

        // 填充数组，动态规划的过程
        for (int i = 1; i <= fruits.length; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    // 选择装入当前水果或不装入的情况，取最大值
                    dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
                } else {
                    // 当前水果的重量大于背包承重，不能装入
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // 打印装水果的策略
        printStrategy(dp, fruits, weights, values, capacity);
    }

    // 打印具体的装水果策略
    private static void printStrategy(int[][] dp, String[] fruits, int[] weights, int[] values, int capacity) {
        int i = fruits.length;
        int w = capacity;

        System.out.println("背包装水果的策略：");

        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                // 当前水果被选中，打印信息
                System.out.println("装入 " + fruits[i - 1] + "，重量：" + weights[i - 1] + "kg，价值：" + values[i - 1]);
                w -= weights[i - 1];
            }
            i--;
        }
    }
}