编辑代码

#include <stdio.h>
#include <string.h>
struct Funtion {
    char name[20];
    int daytimes;
    int rating;
};
void optimizeTravelPlan(struct Funtion funtions[], int n, int days) {
    int dp[days + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        if (funtions[i].daytimes > days) // 超过总旅行天数的景点无法游览
            continue;
        for (int j = days; j >= funtions[i].daytimes; j--) {
            dp[j] = dp[j] > dp[j - funtions[i].daytimes] + funtions[i].rating ? dp[j] : 
                dp[j - funtions[i].daytimes] + funtions[i].rating;
        }
    }
    printf("最大价值: %d\n", dp[days]);
    printf("旅行路线：\n");
    int remainDays = days;
    for (int i = n - 1; i >= 0; i--) {
        if (remainDays >= funtions[i].daytimes && dp[remainDays] == 
            dp[remainDays - funtions[i].daytimes] + funtions[i].rating) 
        {
            printf("%s\n", funtions[i].name);
            remainDays -= funtions[i].daytimes;
        }
    }
}
int main() {
    struct Funtion funtions[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };
    int n = sizeof(funtions) / sizeof(funtions[0]);
    int days = 4;
    optimizeTravelPlan(funtions, n, days);
    return 0;
}