编辑代码

#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];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        for (int j = days; j >= sights[i].daysRequired; 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;
    for (int i = n - 1; i >= 0; i--) {
        if (remainDays >= sights[i].daysRequired && dp[remainDays] == 
                                                dp[remainDays - sights[i].daysRequired] + sights[i].rating) 
        {
            printf("%s\n", sights[i].name);
            remainDays -= sights[i].daysRequired;
        }
    }
}

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;
}