编辑代码

#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int knapsack(int max_time, int weights[], int values[], int num_attractions) {
    int dp[num_attractions + 1][max_time + 1];

    for (int i = 0; i <= num_attractions; i++) {
        for (int w = 0; w <= max_time; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = MAX(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    int res = dp[num_attractions][max_time];
    int w = max_time;
    int selected_attractions[num_attractions];
    int j = 0;

    for (int i = num_attractions; i > 0 && res > 0; i--) {
        if (res == dp[i - 1][w]) {
            continue;
        } else {
            selected_attractions[j++] = i - 1;
            res -= values[i - 1];
            w -= weights[i - 1];
        }
    }

    printf("以下是您可以获得的最大价值的景点：\n");
    for (int i = j - 1; i >= 0; i--) {
        printf("%d. %s\n", j - i, attractions[selected_attractions[i]].name);
    }

    return dp[num_attractions][max_time];
}

int main() {
    int max_time = 4;
    Attraction attractions[] = {{"故宫", 1, 7}, {"颐和园", 2, 8}, {"长城", 3, 9}, {"天坛", 1, 6}};
    int num_attractions = sizeof(attractions) / sizeof(attractions[0]);
    int weights[num_attractions];
    int values[num_attractions];

    for (int i = 0; i < num_attractions; i++) {
        weights[i] = attractions[i].time;
        values[i] = attractions[i].rating;
    }

    knapsack(max_time, weights, values, num_attractions);

    return 0;
}