编辑代码

public class TravelOptimization {  
    public static void main(String[] args) {  
        String[] sights = {  
            "故宫",   
            "颐和园",   
            "长城",   
            "天坛"  
        };  
          
        int[] times = {1, 2, 3, 1};  
        int[] scores = {7, 8, 9, 6};  
        int days = 4;  
          
        int[][] dp = new int[sights.length + 1][days + 1];  
          
        for (int i = 1; i <= sights.length; i++) {  
            for (int j = 1; j <= days; j++) {  
                if (j >= times[i - 1]) {  
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - times[i - 1]] + scores[i - 1]);  
                } else {  
                    dp[i][j] = dp[i - 1][j];  
                }  
            }  
        }  
          
        int maxScore = dp[sights.length][days];  
        System.out.println("最大价值为：" + maxScore);  
        System.out.println("可以获得最大价值的景点是：");  
        int j = days;  
        for (int i = sights.length; i > 0; i--) {  
            if (dp[i][j] != dp[i - 1][j]) {  
                System.out.println(sights[i - 1] + "，时间：" + times[i - 1] + "天，评分：" + scores[i - 1]);  
                j -= times[i - 1];  
            }  
        }  
    }  
}