编辑代码

#include <iostream>
#include <vector>
using namespace std;

// 景点信息
struct Spot {
    string name;  // 景点名称
    int time;     // 景点所需时间
    int score;    // 景点评分
};

void printOptimizedTravelPlan(const vector<Spot>& spots, int totalDays) {
    int n = spots.size();  // 景点数量
    vector<vector<int>> dp(n + 1,
                           vector<int>(totalDays + 1, 0));  // 动态规划数组
    vector<vector<bool>> choice(
        n + 1, vector<bool>(totalDays + 1, false));  // 记录选择情况

    // 动态规划计算最大评分
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= totalDays; j++) {
            int currTime = spots[i - 1].time;
            int currScore = spots[i - 1].score;
            if (currTime > j) {
                // 当前景点所需时间大于剩余天数，无法选择
                dp[i][j] = dp[i - 1][j];
                choice[i][j] = false;
            } else {
                int scoreWithSpot =
                    dp[i - 1][j - currTime] + currScore;  // 去这个景点的总评分
                int scoreWithoutSpot = dp[i - 1][j];  // 不去这个景点的总评分
                if (scoreWithSpot > scoreWithoutSpot) {
                    // 如果去这个景点的评分更高，则选择去这个景点
                    dp[i][j] = scoreWithSpot;
                    choice[i][j] = true;
                } else {
                    // 否则不选择这个景点
                    dp[i][j] = scoreWithoutSpot;
                    choice[i][j] = false;
                }
            }
        }
    }

    // 回溯选取的景点
    int remainingDays = totalDays;
    vector<string> selectedSpots;
    for (int i = n; i >= 1; i--) {
        if (choice[i][remainingDays]) {
            selectedSpots.push_back(spots[i - 1].name);
            remainingDays -= spots[i - 1].time;
        }
    }
    // 打印最优化旅游计划
    cout << "最优化旅游计划: " << endl;
    cout << "总评分: " << dp[n][totalDays] << endl;
    cout << "选择的景点: ";
    for (auto it = selectedSpots.rbegin(); it != selectedSpots.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    // 景点列表和旅行总天数
    vector<Spot> spots = {
        {"故宫", 1, 7}, {"颐和园", 2, 8}, {"长城", 3, 9}, {"天坛", 1, 6}};
    int totalDays = 4;
    // 调用函数打印最优化旅游计划
    printOptimizedTravelPlan(spots, totalDays);
    return 0;
}