编辑代码

#include <stdio.h>

// 定义景点结构体
typedef struct {
    char name[20];
    int time;
    int score;
} Attraction;

// 函数声明
void optimize_travel(int days_available, Attraction attractions[], int num_attractions);

int main() {
    // 定义景点数组
    Attraction attractions[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };

    // 总共4天
    int days_available = 4;

    // 获取景点数量
    int num_attractions = sizeof(attractions) / sizeof(attractions[0]);

    // 调用函数进行优化
    optimize_travel(days_available, attractions, num_attractions);

    return 0;
}

// 旅游行程最优化函数
void optimize_travel(int days_available, Attraction attractions[], int num_attractions) {
    int dp[num_attractions + 1][days_available + 1];

    for (int i = 0; i <= num_attractions; i++) {
        for (int j = 0; j <= days_available; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (attractions[i - 1].time <= j) {
                dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - attractions[i - 1].time] + attractions[i - 1].score)
                               ? dp[i - 1][j]
                               : dp[i - 1][j - attractions[i - 1].time] + attractions[i - 1].score;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 输出最大价值
    printf("最大价值：%d\n", dp[num_attractions][days_available]);

    // 输出选择的景点
    printf("选择的景点：\n");
    int i = num_attractions, j = days_available;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("%s\n", attractions[i - 1].name);
            j -= attractions[i - 1].time;
        }
        i--;
    }
}