编辑代码

import java.util.HashMap;
import java.util.Map;

public class TravelOptimization {

    static class Sightseeing {
        String name;
        int days;
        int score;

        Sightseeing(String name, int days, int score) {
            this.name = name;
            this.days = days;
            this.score = score;
        }
    }

    public static void main(String[] args) {
        // 定义景点信息
        Sightseeing[] sights = {
                new Sightseeing("故宫", 1, 7),
                new Sightseeing("颐和园", 2, 8),
                new Sightseeing("长城", 3, 9),
                new Sightseeing("天坛", 1, 6)
        };

        // 定义总旅行天数
        int totalDays = 4;

        // 使用哈希映射来存储每一天可能的最大评分
        Map<String, Integer> dp = new HashMap<>();
        dp.put("", 0);

        // 遍历每个景点
        for (int i = 0; i < sights.length; i++) {
            Sightseeing sight = sights[i];

            // 创建新的哈希映射用于存储更新后的状态
            Map<String, Integer> newDp = new HashMap<>(dp);

            // 遍历之前的状态
            for (Map.Entry<String, Integer> entry : dp.entrySet()) {
                String prevKey = entry.getKey();
                int prevScore = entry.getValue();
                int newDays = 0;
                int newScore = 0;

                // 计算新的旅行天数和评分
                for (int j = 0; j < prevKey.length(); j++) {
                    if (prevKey.charAt(j) == '1') {
                        newDays++;
                    }
                }

                // 判断新的天数是否符合限制
                if (newDays + sight.days <= totalDays) {
                    newDays += sight.days;
                    newScore = prevScore + sight.score;

                    // 构造新的状态字符串
                    String newKey = prevKey + i;

                    // 更新新的状态
                    newDp.put(newKey, Math.max(newDp.getOrDefault(newKey, 0), newScore));
                }
            }

            // 更新状态
            dp = newDp;
        }

        // 寻找最大评分和对应的景点组合
        int maxScore = 0;
        String bestCombination = "";

        for (Map.Entry<String, Integer> entry : dp.entrySet()) {
            if (entry.getValue() > maxScore) {
                maxScore = entry.getValue();
                bestCombination = entry.getKey();
            }
        }

        // 打印结果
        System.out.println("最大评分为：" + maxScore);
        System.out.print("选择的景点为：");
        for (int i = 0; i < bestCombination.length(); i++) {
            if (bestCombination.charAt(i) == '0') continue;
            System.out.print(sights[i].name + " ");
        }
    }
}