// 导入Java的ArrayList类，该类提供动态数组的功能，可快速地添加和删除元素。
import java.util.ArrayList;
// 导入Java的List接口，它是一个有序的集合，并可包含重复的元素。
import java.util.List;
// 定义一个公共类ItineraryOptimization。
public class ItineraryOptimization {
// 定义一个静态内部类Spot，表示景点。包含两个属性：时间（天数）和评分。
static class Spot {
int time; // 景点所需时间（天数）
int score; // 景点评分
// 定义Spot的构造函数，接受时间和评分作为参数。
Spot(int time, int score) {
this.time = time; // 设置时间属性值
this.score = score; // 设置评分属性值
}
}
// 定义一个静态方法optimizeItinerary，用于优化行程。接受时间数组、评分数组和总天数作为参数。
public static List<Spot> optimizeItinerary(int[] times, int[] scores, int totalDays) {
// 获取时间数组和评分数组的长度，用于初始化dp数组的大小。
int numSpots = times.length;
// 定义一个二维数组dp，用于存储每个子问题的最优解。dp[i][j]表示前i个景点中，在j天内的最大评分。
int[][] dp = new int[numSpots + 1][totalDays + 1];
// 使用两层循环遍历所有景点和所有天数。
for (int i = 1; i <= numSpots; i++) { // i表示当前考虑的景点索引（从1开始）
for (int j = 1; j <= totalDays; j++) { // j表示当前考虑的天数（从1开始）
// 如果当前景点的时间小于等于剩余天数，则有两种选择：包含当前景点或不包含当前景点。
if (times[i - 1] <= j) { // times[i - 1]表示第i个景点所需的时间。
// 计算两种选择中的最大值，并存储到dp数组中。
dp[i][j] = Math.max(dp[i - 1][j], scores[i - 1] + dp[i - 1][j - times[i - 1]]);
} else { // 如果当前景点的时间大于剩余天数，则只能选择不包含当前景点。
dp[i][j] = dp[i - 1][j]; // 继承前一个状态的值。
}
}
}
// 初始化一个ArrayList来存储选中的景点。
List<Spot> selectedSpots = new ArrayList<>();
// 用两个变量i和j来追踪当前考虑的景点和剩余的天数。从最后一个景点开始回溯。
int i = numSpots; // i表示当前考虑的景点索引（从numSpots开始递减）
int j = totalDays; // j表示当前考虑的天数（从totalDays开始递减）
// 使用while循环回溯到第一个景点，同时更新selectedSpots列表和剩余天数j。
while (i > 0 && j > 0) { // 当还有景点和天数时继续循环。
if (dp[i][j] != dp[i - 1][j]) { // 如果当前状态的值与上一个状态的值不同，说明当前景点是有利的。
selectedSpots.add(new Spot(times[i - 1], scores[i - 1])); // 将当前景点添加到selectedSpots列表中。
j -= times[i - 1]; // 从剩余天数中减去当前景点的天数。
}
i--; // 考虑下一个景点。
}
return selectedSpots; // 返回选中的景点列表。
}
public static void main(String[] args) { // 主函数，程序的入口点。
// 定义景点所需的时间和评分数组。总共有4个景点。
int[] times = {1, 2, 3, 1}; // 第0个景点需要1天，第1个景点需要2天，第2个景点需要3天，第3个景点需要1天。
int[] scores = {7, 8, 9, 6}; // 第0个景点的评分为7，第1个景点的评分为8，第2个景点的评分为9，第3个景点的评分为6。
// 定义总的旅游天数。
int totalDays = 4; // 总共可以旅游4天。
// 调用optimizeItinerary方法，传入时间、评分和总天数参数，得到一个最优化的行程列表。
List<Spot> optimizedItinerary = optimizeItinerary(times, scores, totalDays);
// 打印最优化的旅游行程。
System.out.println("最优化的旅游行程:");
for (Spot spot : optimizedItinerary) { // 遍历每个选中的景点。
System.out.println("景点时间：" + spot.time + "天，景点评分：" + spot.score); // 打印景点的时间和评分。
}
}
}