编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[20];
    int time;
    int score;
} ScenicSpot;

int main() {
    ScenicSpot spots[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };
    int spotCount = sizeof(spots) / sizeof(ScenicSpot);

    int days = 4;
    int **dp = (int **)malloc((spotCount + 1) * sizeof(int *));
    for (int i = 0; i <= spotCount; ++i) {
        dp[i] = (int *)malloc((days + 1) * sizeof(int));
    }

    for (int i = 0; i <= spotCount; ++i) {
        for (int j = 0; j <= days; ++j) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (spots[i - 1].time <= j) {
                int value1 = spots[i - 1].score + dp[i - 1][j - spots[i - 1].time];
                int value2 = dp[i - 1][j];
                dp[i][j] = (value1 > value2) ? value1 : value2;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    int maxValue = dp[spotCount][days];
    printf("最大值为：%d\n", maxValue);

    printf("景点是：");
    int i = spotCount, j = days;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("%s ", spots[i - 1].name);
            j -= spots[i - 1].time;
        }
        --i;
    }
    printf("\n");

    for (int i = 0; i <= spotCount; ++i) {
        free(dp[i]);
    }
    free(dp);

    return 0;
}