编辑代码

#include <stdio.h>
#include <string.h>

struct Sight {
    char name[20];
    int daysRequired;
    int rating;
};

void findMaxValue(struct Sight sights[], int n, int days) {
    int dp[days + 1]; // 创建一个长度为 days+1 的数组，用于存储最大价值
    memset(dp, 0, sizeof(dp)); // 将 dp 数组初始化为 0

    for (int i = 0; i < n; i++) { // 遍历每个景点
        for (int j = days; j >= sights[i].daysRequired; j--) { // 从总天数开始向前遍历
            // 更新 dp[j]，如果当前景点的天数要求小于等于当前剩余天数
            // 则比较是否选择当前景点能够获得更大的价值，并更新 dp[j]
            dp[j] = dp[j] > dp[j - sights[i].daysRequired] + sights[i].rating ? dp[j] : dp[j - sights[i].daysRequired] + sights[i].rating;
        }
    }
    printf("最大价值: %d\n", dp[days]);

    // 回溯找到实际的旅行路线
    printf("旅行路线：\n");
    int remainDays = days;
    char travelRoute[100] = ""; // 存储旅行路线的字符串变量
    for (int i = n - 1; i >= 0; i--) { // 从最后一个景点开始回溯
        if (remainDays >= sights[i].daysRequired && dp[remainDays] == dp[remainDays - sights[i].daysRequired] + sights[i].rating) {
            // 如果当前景点满足剩余天数要求，并且选择当前景点能够获得最大价值，则将当前景点添加到旅行路线中
            strcat(travelRoute, sights[i].name); // 将当前景点名称添加到旅行路线中
            strcat(travelRoute, " ");
            remainDays -= sights[i].daysRequired; // 减去当前景点的天数要求
        }
    }
    printf("%s\n", travelRoute); // 打印旅行路线
}

int main() {
    struct Sight sights[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };
    int n = sizeof(sights) / sizeof(sights[0]); // 获取景点数组的长度
    int days = 4; // 总天数

    findMaxValue(sights, n, days); // 调用函数计算最大价值和旅行路线

    return 0;
}