编辑代码

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

public class TestQiMo {
    public static void main(String[] args) {
        String[] attractions = { "故宫", "颐和园", "长城", "天坛"};
        int[] time = {1, 2, 3, 1};
        int[] pinfen = {7, 8, 9, 6};
        int useTime = 4;
        List<String> bestAttractions = fund(attractions, time, pinfen, useTime);
        System.out.println("最优化旅游景点路径：");
        for (String attraction : bestAttractions) {
            System.out.println(attraction);
        }
    }

    public static List<String> fund(String[] attractions, int[] time, int[] pinfen, int useTime) {
        int n = attractions.length;
        int[][] dp = new int[n + 1][useTime + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= useTime; j++) {
                if (time[i-1] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j], pinfen[i-1] + dp[i-1][j-time[i-1]]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        int i = n;
        int j = useTime;
        List<String> bestAttractions = new ArrayList<>();
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i-1][j]) {
                bestAttractions.add(attractions[i-1]);
                j -= time[i-1];
            }
            i--;
        }
        return bestAttractions;
    }
}