编辑代码

#include <stdio.h>

#define MAX_DAYS 4
#define MAX_SPOTS 4

// 用于存放景点信息的结构体
typedef struct {
    int time;   // 访问时间（单位：天）
    int score;  // 评分
} Spot;

// 动态规划解决问题
void travelPlan(Spot spots[], int n, int maxTime) {
    int dp[MAX_SPOTS + 1][MAX_DAYS + 1] = {0};

    // 构建dp表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxTime; j++) {
            if (j >= spots[i - 1].time) {
                // 可以选择去这个景点
                dp[i][j] = (dp[i - 1][j] > (dp[i - 1][j - spots[i - 1].time] + spots[i - 1].score)) ? dp[i - 1][j] : (dp[i - 1][j - spots[i - 1].time] + spots[i - 1].score);
            } else {
                // 无法去这个景点，保留前i-1个景点的最优解
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 找出最大评分对应的景点组合
    int j = maxTime;
    for (int i = n; i > 0; i--) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("访问景点编号：%d (评分：%d, 时间：%d天)\n", i, spots[i - 1].score, spots[i - 1].time);
            j -= spots[i - 1].time;
        }
    }

    printf("最大总评分：%d\n", dp[n][maxTime]);
}

// 主函数
int main() {
    Spot spots[MAX_SPOTS] = {
        {1, 7}, // 故宫
        {2, 8}, // 颐和园
        {3, 9}, // 长城
        {1, 6}  // 天坛
    };

    travelPlan(spots, MAX_SPOTS, MAX_DAYS);
    return 0;
}