编辑代码

const optimizeTravel = (schedule, totalDays) => {
    const numSpots = schedule.length;

    // 初始化动态规划表格存储最大价值
    const dp = Array.from({ length: numSpots + 1 }, () => Array(totalDays + 1).fill(0));

    for (let i = 1; i <= numSpots; i++) {
        for (let j = 1; j <= totalDays; j++) {
            // 如果当前景点所需时间小于等于剩余时间，考虑是否选择该景点
            if (schedule[i - 1].time <= j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - schedule[i - 1].time] + schedule[i - 1].score);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 回溯找到被选择的景点
    const selectedSpots = [];
    let i = numSpots;
    let j = totalDays;
    while (i > 0 && j > 0) {
        if (dp[i][j] !== dp[i - 1][j]) {
            selectedSpots.push(schedule[i - 1]);
            j -= schedule[i - 1].time;
        }
        i--;
    }

    return selectedSpots;
}



const travelSchedule = [
    { spot: '故宫', time: 1, score: 7 },
    { spot: '颐和园', time: 2, score: 8 },
    { spot: '长城', time: 3, score: 9 },
    { spot: '天坛', time: 1, score: 6 },
];

const totalTravelDays = 4;

const result = optimizeTravel(travelSchedule, totalTravelDays);

console.log("最优行程包括的景点：");
for (const spot of result) {
    console.log(`${spot.spot} (时间：${spot.time}天, 评分：${spot.score})`);
}