编辑代码

public class TravelOptimization {

    // 动态规划算法
    public static void travelOptimization(int days, int[] time, int[] score) {
        int[][] dp = new int[days + 1][time.length + 1];

        for (int i = 1; i <= days; i++) {
            for (int j = 1; j <= time.length; j++) {
                if (time[j - 1] <= i) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - time[j - 1]][j - 1] + score[j - 1]);
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        int result = dp[days][time.length];
        System.out.println("最大价值为：" + result);
        System.out.println("选择的景点为：");

        int remainingDays = days;
        for (int j = time.length; j > 0 && result > 0; j--) {
            if (dp[remainingDays][j] != dp[remainingDays][j - 1]) {
                System.out.println("景点" + j + ": 时间=" + time[j - 1] + "天, 评分=" + score[j - 1]);
                remainingDays -= time[j - 1];
                result -= score[j - 1];
            }
        }
    }

    public static void main(String[] args) {
        int days = 4;
        int[] time = {1, 2, 3, 1};
        int[] score = {7, 8, 9, 6};

        travelOptimization(days, time, score);
    }
}