编辑代码

class main {

    public static void findBestItinerary(String[] attractions, int[] durations, int[] scores, int days) {
        int[][] dp = new int[attractions.length + 1][days + 1];

        // 填充动态规划表格
        for (int i = 1; i <= attractions.length; i++) {
            for (int j = 1; j <= days; j++) {
                // 当前景点不去
                int notGo = dp[i - 1][j];
                
                // 当前景点去
                int go = 0;
                if (j >= durations[i - 1]) {
                    go = dp[i - 1][j - durations[i - 1]] + scores[i - 1];
                }

                // 选择去或者不去的最大值
                dp[i][j] = Math.max(notGo, go);
            }
        }

        // 从动态规划表格中反向回溯，找到选择的景点
        int i = attractions.length;
        int j = days;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                System.out.println(attractions[i - 1] + "，时间：" + durations[i - 1] + "天，评分：" + scores[i - 1]);
                j -= durations[i - 1];
            }
            i--;
        }
    }

    public static void main(String[] args) {
        // 景点信息
        String[] attractions = {"故宫", "颐和园", "长城", "天坛"};
        int[] durations = {1, 2, 3, 1};
        int[] scores = {7, 8, 9, 6};

        // 假期为4天
        int days = 4;

        // 找到最优行程
        findBestItinerary(attractions, durations, scores, days);
    }
}