编辑代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<SightseeingSpot> spots = new ArrayList<>();
        spots.add(new SightseeingSpot("故宫", 1, 7));
        spots.add(new SightseeingSpot("颐和园", 2, 8));
        spots.add(new SightseeingSpot("长城", 3, 9));
        spots.add(new SightseeingSpot("天坛", 1, 6));

        int totalDays = 4;

        Result result = optimizeTrip(spots, totalDays);

        System.out.println("最优化的旅游行程：");
        for (SightseeingSpot spot : result.selectedSpots) {
            System.out.println(spot.name + " - 时间：" + spot.time + "天，评分：" + spot.score);
        }
        System.out.println("最高总分：" + result.totalScore);
    }

    // 用于存储最优化的旅游行程和最高总分的结果类
    public static class Result {
        List<SightseeingSpot> selectedSpots;  // 被选择的景点列表
        int totalScore;  // 最高总分

        public Result(List<SightseeingSpot> selectedSpots, int totalScore) {
            this.selectedSpots = selectedSpots;
            this.totalScore = totalScore;
        }
    }

    // 优化旅游行程的方法
    public static Result optimizeTrip(List<SightseeingSpot> spots, int totalDays) {
        int n = spots.size();
        int[][] dp = new int[n + 1][totalDays + 1];  // 创建二维数组dp，用于存储子问题的最优解

        // 填充dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= totalDays; j++) {
                if (spots.get(i - 1).time > j) {
                    dp[i][j] = dp[i - 1][j];  // 如果当前景点的时间超过了剩余可用时间，则不选择当前景点
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - spots.get(i - 1).time] + spots.get(i - 1).score);  // 否则比较选择当前景点和不选择当前景点两种情况下的评分
                }
            }
        }

        List<SightseeingSpot> selectedSpots = new ArrayList<>();
        int j = totalDays;
        for (int i = n; i > 0; i--) {
            if (dp[i][j] != dp[i - 1][j]) {  // 根据dp数组的结果，回溯得到最优化的旅游行程
                selectedSpots.add(spots.get(i - 1));
                j -= spots.get(i - 1).time;
            }
        }

        Collections.reverse(selectedSpots);
        return new Result(selectedSpots, dp[n][totalDays]);  // 返回最优化的旅游行程和最高总分
    }
}

// 景点类
class SightseeingSpot {
    String name;  // 景点名称
    int time;     // 参观所需时间
    int score;    // 评分

    public SightseeingSpot(String name, int time, int score) {
        this.name = name;
        this.time = time;
        this.score = score;
    }
}