编辑代码

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

class main {

    // 定义一个内部类表示水果
    public static class Fruit {
        String name; // 水果名称
        int weight;  // 水果重量
        int value;   // 水果价值

        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[][] dp = new int[fruits.length + 1][capacity + 1];

        // 动态规划填表
        for (int i = 1; i <= fruits.length; i++) {
            for (int w = 1; w <= capacity; w++) {
                for (int k = 0; k <= fruits[i - 1].weight; k++) {
                    if (k <= w) {
                        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - k] + k * fruits[i - 1].value / fruits[i - 1].weight);
                    }
                }
            }
        }

        // 从动态规划表中回溯找出装入水果的策略
        List<String> strategy = new ArrayList<>();
        int i = fruits.length;
        int w = capacity;
        while (i > 0 && w > 0) {
            for (int k = 0; k <= fruits[i - 1].weight; k++) {
                if (k <= w && dp[i][w] == dp[i - 1][w - k] + k * fruits[i - 1].value / fruits[i - 1].weight) {
                    if (k > 0) { // 检查是否装入了水果
                        strategy.add("装入 " + fruits[i - 1].name + " " + k + "kg");
                    }
                    w -= k;
                    break;
                }
            }
            i--;
        }

        // 输出装水果的策略
        for (int j = strategy.size() - 1; j >= 0; j--) {
            System.out.println(strategy.get(j));
        }

        // 输出总价值
        System.out.println("总价值：" + dp[fruits.length][capacity]);
    }
}