编辑代码

public class test2 {
    public static void main(String[] args) {
        // 景点信息
        String[] attractions = {"故宫", "颐和园", "长城", "天坛"};
        int[] times = {1, 2, 3, 1};  // 每个景点需要的时间
        int[] scores = {7, 8, 9, 6};  // 每个景点的评分
        int totalDays = 4;  // 总旅行天数

        // 创建二维数组，dp[i][j] 表示在前 i 个景点中，占用 j 天时能够获得的最大总评分
        int[][] dp = new int[attractions.length + 1][totalDays + 1];

        // 填充dp数组
        for (int i = 1; i <= attractions.length; i++) {
            for (int j = 1; j <= totalDays; j++) {
                if (times[i - 1] <= j) {
                    // 选择当前景点或不选择当前景点，取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], scores[i - 1] + dp[i - 1][j - times[i - 1]]);
                } else {
                    // 当前景点的时间超过剩余天数，不能选择
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // 打印最优的旅游行程
        printOptimalTravel(dp, attractions, times, totalDays);
    }

    // 打印最优的旅游行程
    private static void printOptimalTravel(int[][] dp, String[] attractions, int[] times, int totalDays) {
        int i = attractions.length;
        int j = totalDays;

        System.out.println("最优的旅游行程：");

        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                // 当前景点被选择
                System.out.println(attractions[i - 1] + "，需要时间：" + times[i - 1] + "天，评分：" + dp[i][j]);
                j -= times[i - 1];
            }
            i--;
        }
    }
}