编辑代码

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