编辑代码

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

public class QuestionTwo {
    public static void main(String[] args) {
        String[] attractions = {"故宫", "颐和园", "长城", "天坛"};
        int[] time = {1, 2, 3, 1};
        int[] score = {7, 8, 9, 6};
        int days = 4;

        List<String> selectedAttractions = optimizeTravel(attractions, time, score, days);

        int maxScore = calculateScore(selectedAttractions, attractions, score);
        System.out.println("最大价值为：" + maxScore);

        System.out.print("选择的景点有：");
        for (String attraction : selectedAttractions) {
            System.out.print(attraction + " ");
        }
    }

    public static List<String> optimizeTravel(String[] attractions, int[] time, int[] score, int days) {
        int n = attractions.length;

        int[][] dp = new int[n + 1][days + 1];

        // 动态规划，计算最大价值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= days; j++) {
                if (time[i - 1] <= j) {
                    // 如果第i个景点可以在j天内访问，则比较选择去和不去的情况，取较大值
                    dp[i][j] = Math.max(dp[i - 1][j - time[i - 1]] + score[i - 1], dp[i - 1][j]);
                } else {
                    // 如果第i个景点需要的天数大于j，则无法选择去这个景点
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        List<String> selectedAttractions = new ArrayList<>();
        int i = n;
        int j = days;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                // 如果选择了第i个景点，则将其添加到选择列表中，并更新剩余天数j
                selectedAttractions.add(attractions[i - 1]);
                j -= time[i - 1];
            }
            i--;
        }

        return selectedAttractions;
    }

    public static int calculateScore(List<String> selectedAttractions, String[] attractions, int[] score) {
        int totalScore = 0;
        for (String attraction : selectedAttractions) {
            for (int i = 0; i < attractions.length; i++) {
                if (attraction.equals(attractions[i])) {
                    totalScore += score[i];
                    break;
                }
            }
        }
        return totalScore;
    }
}