import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
class Main {
static class Location {
String name;
Integer time;
Integer score;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getTime() {
return time;
}
public void setTime(Integer time) {
this.time = time;
}
public Integer getScore() {
return score;
}
public void setScore(Integer score) {
this.score = score;
}
}
static class TravelOptimize {
int weight;
private int[][] dp;
private List<Location> locations;
public TravelOptimize(List<Location> locations, int weight) {
this.locations = locations;
this.weight = weight;
int len = locations.size();
dp = new int[len + 1][weight + 1];
for (int i = 0; i < len + 1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i < weight + 1; i++) {
dp[0][i] = 0;
}
}
public Integer findMaxValuePath() {
if (Objects.isNull(locations) || locations.isEmpty()) {
return 0;
}
for (int i = 1; i <= locations.size(); i++) {
Location curLocation = locations.get(i - 1);
for (int j = 1; j <= weight; j++) {
if (j - curLocation.time >= 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - curLocation.time] + curLocation.score);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i <= weight; i++) {
maxValue = Math.max(dp[locations.size()][i], maxValue);
}
return maxValue;
}
public int[][] getDp() {
return dp;
}
public void printLocation() {
LinkedList<String> locationNames = new LinkedList<>();
for (int i = locations.size() - 1; i >= 0; i--) {
Location location = locations.get(i);
for (int j = weight; j > 0; j--) {
if (dp[i + 1][j] == dp[i + 1][j-1]) {
continue;
} else {
if (dp[i + 1][j] == (location.score + dp[i][j - location.time])) {
locationNames.addFirst(location.name);
weight -= location.time;
}
break;
}
}
}
for (int i = 0; i < locationNames.size(); i++) {
System.out.printf(locationNames.get(i));
if (i < locationNames.size() - 1) {
System.out.printf("->");
}
}
}
}
public static void main(String[] args) {
Location location1 = new Location();
location1.setName("故宫");
location1.setTime(1);
location1.setScore(7);
Location location2 = new Location();
location2.setName("颐和园");
location2.setTime(2);
location2.setScore(8);
Location location3 = new Location();
location3.setName("长城");
location3.setTime(3);
location3.setScore(9);
Location location4 = new Location();
location4.setName("天坛");
location4.setTime(1);
location4.setScore(6);
List<Location> locationList = new ArrayList<>();
locationList.add(location1);
locationList.add(location2);
locationList.add(location3);
locationList.add(location4);
int day = 4;
TravelOptimize travelOptimize = new TravelOptimize(locationList, day);
Integer maxValuePath = travelOptimize.findMaxValuePath();
System.out.println(maxValuePath);
travelOptimize.printLocation();
System.out.println();
}
}