编辑代码

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

public class OptimalTour {
    static class Sightseeing {
    String name;
    int time;
    int score;
    public Sightseeing(String name, int time, int score) {
        this.name = name;
        this.time = time;
        this.score = score;
        }
    }

    public static void main(String[] args) {
        System.out.println("20052218 刘嘉源");
        List<Sightseeing> sights = new ArrayList<>();
        sights.add(new Sightseeing("故宫", 1, 7));
        sights.add(new Sightseeing("颐和园", 2, 8));
        sights.add(new Sightseeing("长城", 3, 9));
        sights.add(new Sightseeing("天坛", 1, 6));
        int days = 4;
        int[][] dp = new int[sights.size() + 1][days + 1];
        for (int i = 1; i <= sights.size(); i++) {
            Sightseeing sight = sights.get(i - 1);
            for (int j = 1; j <= days; j++) {
                if (sight.time > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - sight.time] + sight.score);
                }
            }
        }
        int result = dp[sights.size()][days];
        System.out.println("最大价值为: " + result);
        System.out.println("去过的景点有:");
        int remainingDays = days;
        for (int i = sights.size(); i > 0 && result > 0; i--) {
            if (result != dp[i - 1][remainingDays]) {
                Sightseeing sight = sights.get(i - 1);
                System.out.println(sight.name);
                result -= sight.score;
                remainingDays -= sight.time;
            }
        }
    }
}