编辑代码

#include <stdio.h>

#define NUM_SIGHT 4
#define MAX_DAYS 4

struct sightseeing {
    char name[20];
    int time;
    int score;
};

// 返回最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 输出函数
void printSelectedSight(int dp[][MAX_DAYS + 1], struct sightseeing s_see[]) {
    printf("去以下景点：\n");
    int i = NUM_SIGHT;
    int j = MAX_DAYS;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("%s (时间：%d天, 评分：%d)\n", s_see[i - 1].name, s_see[i - 1].time, s_see[i - 1].score);
            j -= s_see[i - 1].time;
        }
        i--;
    }
}

// 动态规划求解最大评分
int maxScore(struct sightseeing s_see[]) {
    int dp[NUM_SIGHT + 1][MAX_DAYS + 1] = {0};

    for (int i = 1; i <= NUM_SIGHT; i++) {
        for (int j = 1; j <= MAX_DAYS; j++) {
            if (s_see[i - 1].time <= j) {
                dp[i][j] = max(s_see[i - 1].score + dp[i - 1][j - s_see[i - 1].time], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    printSelectedSight(dp, s_see);

    return dp[NUM_SIGHT][MAX_DAYS];
}

int main() {
    struct sightseeing s_see[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };

    int maxScoreValue = maxScore(s_see);

    printf("在%d天内能获得最大价值为：%d\n", MAX_DAYS, maxScoreValue);

    return 0;
}