编辑代码

#include <stdio.h>

// Define structure for attractions
typedef struct {
    char attraction_name[20];
    int time_required;
    int attraction_score;
} Attraction;

// Function declaration
void optimize_travel(int available_days, Attraction attractions[], int num_attractions);

int main() {
    // Define array of attractions
    Attraction attractions[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };

    // Total available days is 4
    int available_days = 4;

    // Get the number of attractions
    int num_attractions = sizeof(attractions) / sizeof(attractions[0]);

    // Call the function to optimize the travel itinerary
    optimize_travel(available_days, attractions, num_attractions);

    return 0;
}

// Function to optimize travel itinerary
void optimize_travel(int available_days, Attraction attractions[], int num_attractions) {
    int dp[num_attractions + 1][available_days + 1];

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

    // Output the maximum value
    printf("Maximum value: %d\n", dp[num_attractions][available_days]);

    // Output the selected attractions
    printf("Selected attractions:\n");
    int i = num_attractions, j = available_days;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("%s\n", attractions[i - 1].attraction_name);
            j -= attractions[i - 1].time_required;
        }
        i--;
    }
}