编辑代码

import java.util.*;
class Place {
    public String name;
    public int day;
    public int score;

    Place(String n, int d, int s){
        this.name = n;
        this.day = d;
        this.score = s;
    }

	public static void main(String[] args) {
        Place[] places = {
            new Place("故宫",1,7),
            new Place("颐和园",2,8),
            new Place("长城",3,9),
            new Place("天坛",1,6)
        };
        LinkedList<Place> travelPlace = travelPlace(4,places);
        int maxValue = 0;
        System.out.println("去以下地点:");
        for(int i = 0; i < travelPlace.size(); i++){
            System.out.println(travelPlace.get(i).name);
            maxValue += travelPlace.get(i).score;
        }
        System.out.println("最大价值为:" + maxValue);
	}
    public static LinkedList<Place> travelPlace(int allDays,Place[] places){
        int rowCount = places.length + 1;
        int colCount = allDays + 1;
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Place> travelPlace = new LinkedList<Place>();
        // 动态规划计算每个子问题的最优解
        for(int i = 1; i < rowCount; i++){
            for(int j = 1; j < colCount; j++){
                // 如果当前地点可以在当前天数内游玩,选择最大评分
                if(places[i-1].day <= j){
                    dpArray[i][j] = Math.max(places[i-1].score + dpArray[i-1][j-places[i-1].day],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){
            if(dpArray[i][j] != dpArray[i-1][j]){
                travelPlace.addFirst(places[i-1]);
                j = j - places[i - 1].day;
                i--;
            }else{
                i--;
            }
        }
        return travelPlace;
    }
}