编辑代码

import java.util.LinkedList;

public class TravelOptimization {
    public static LinkedList<Place> traveloptionPlaces(int[] days, Place[] places) {
        //确定动态规划表的行和列
        int rowCount = places.length + 1;
        int colCount = days[days.length - 1] + 1;
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Place> selectedPlaces = new LinkedList<Place>();
        for (int i = 1; i < rowCount; ++i) {
            
            int placeTime = places[i - 1].time; 
            for (int j = 1; j < colCount; ++j) {
                if (placeTime <= j){
                    dpArray[i][j] = Math.max(places[i-1].score + dpArray[i - 1][j - placeTime], dpArray[i-1][j]);
                } else {
                    dpArray[i][j] = dpArray[i-1][j];
                }
            }
        }
        int i = rowCount - 1;
        int j = colCount - 1;
        while(i > 0 && j > 0) {
            int placeTime =places[i - 1].time; 
            if (dpArray[i][j] != dpArray[i-1][j]) {
                selectedPlaces.addFirst(places[i-1]);
                j = j - placeTime;
                i = i-1;
            } else {
                i = i - 1;
            }
        }
        return selectedPlaces;
    }
    public static void main(String[] args) {
        //天数选择
        int[] days = {0, 1, 2, 3, 4};
        Place[] places = {
            new Place("故宫", 1, 7),
            new Place("颐和园", 2, 8),
            new Place("长城", 3, 9),
            new Place("天坛", 1, 6)
        };
        LinkedList<Place> selectedPlaces = traveloptionPlaces(days, places);
        int maxValue = 0;
        System.out.println("可以去以下景点：");
        for (Place place : selectedPlaces) {
            System.out.println(place.name);
            maxValue += place.score;
        }
        System.out.println("总评分：" + maxValue);
    }
}
class Place {
    public String name;
    public int time;
    public int score;
    Place(String n, int t, int s) {
        this.name = n;
        this.time = t;
        this.score = s;
    }
}