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;
}
}