编辑代码

class Main {
    public static void travelOptimization(String[] places, int[] time, int[] scores, int days) {
        int[][] dp = new int[places.length][days + 1];	//用于记录每个景点在每个剩余天数下的最优解。
        // 填充动态规划表格，外层循环遍历每个景点，内层循环遍历剩余的天数。
        for (int i = 0; i < places.length; i++) {
            for (int j = 1; j <= days; j++) {
                // 当前景点不去
                int notGo = i > 0 ? dp[i - 1][j] : 0;
                // 当前景点去
                int go = 0;
                if (j >= time[i]) {
                    go = i > 0 ? dp[i - 1][j - time[i]] + scores[i] : scores[i];
                }
                // 选择去或者不去的最大值
                dp[i][j] = Math.max(notGo, go);
            }
        }
        // 从动态规划表格中反向回溯，找到选择的景点
        int i = places.length - 1;
        int j = days;
        while (i >= 0 && j > 0) {
            if (i > 0 && dp[i][j] != dp[i - 1][j]) {
                System.out.println(places[i] + "，时间：" + time[i] + "天，评分：" + scores[i]);
                j -= time[i];
            } else if (i == 0 && dp[i][j] > 0) {
                System.out.println(places[i] + "，时间：" + time[i] + "天，评分：" + scores[i]);
                j -= time[i];
            }
            i--;
        }
    }
    public static void main(String[] args) {
        // 景点信息
        String[] places = {"故宫", "颐和园", "长城", "天坛"};
        int[] time = {1, 2, 3, 1};
        int[] scores = {7, 8, 9, 6};
        // 假期为4天
        int days = 4;
        // 找到最优行程
        travelOptimization(places, time, scores, days);
    }
}