编辑代码

public class Travel_optimization {

    // 动态规划算法
    public static void travel_optimization(int days, int[] time, int[] score,String[] scenic_spot) {
        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 remaining_days = days;
        for (int j = time.length; j > 0 && result > 0; j--) {
            if (dp[remaining_days][j] != dp[remaining_days][j - 1]) {
                System.out.println(scenic_spot[j-1] + ": 时间=" + time[j - 1] + "天, 评分=" + score[j - 1]);
                remaining_days -= 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};
        String[] scenic_spot={"故宫","颐和园","长城","天坛"};
        travel_optimization(days, time, score,scenic_spot);
    }
}