编辑代码

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

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

        int[][] dp = new int[attractions.length][totalDays + 1];

        for (int i = 0; i < attractions.length; i++) {
            for (int j = 1; j <= totalDays; j++) {
                // 如果当前景点需要的时间超过了剩余天数，则无法选择该景点
                if (time[i] > j) {
                    dp[i][j] = (i == 0) ? 0 : dp[i - 1][j];
                } else {
                    // 选择当前景点或者不选择当前景点
                    int choose = (i == 0) ? score[i] : dp[i - 1][j - time[i]] + score[i];
                    int notChoose = (i == 0) ? 0 : dp[i - 1][j];
                    dp[i][j] = Math.max(choose, notChoose);
                }
            }
        }

        // 逆序遍历二维数组，找到选择的最优解
        int j = totalDays;
        List<String> selectedAttractions = new ArrayList<>();
        for (int i = attractions.length - 1; i >= 0; i--) {
            if (i == 0) {
                if (dp[i][j] != dp[i][j - 1]) {
                    selectedAttractions.add(attractions[i]);
                }
            } else {
                if (dp[i][j] != dp[i - 1][j]) {
                    selectedAttractions.add(attractions[i]);
                    j -= time[i];
                }
            }
        }

        Collections.reverse(selectedAttractions);
        for (String attraction : selectedAttractions) {
            System.out.println(attraction);
        }
    }
}