编辑代码

#include <stdio.h>

typedef struct {
    char name[10];
    int time;
    int score;
} Spot;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    Spot spots[4] = {{"故宫", 1, 7}, {"颐和园", 2, 8}, {"长城", 3, 9}, {"天坛", 1, 6}};
    int n = sizeof(spots) / sizeof(spots[0]);
    int m = 4;
    int dp[n][m+1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0) {
                dp[i][j] = (j >= spots[i].time) ? spots[i].score : 0;
            } else {
                if (j >= spots[i].time) {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-spots[i].time] + spots[i].score);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }
    
    printf("去哪些景点能够获得最大价值：\n");
    int i = n - 1, j = m;
    while (i > 0 && j >= spots[i].time) {
        if (dp[i][j] == dp[i-1][j]) {
            i--;
        } else {
            printf("%s\n", spots[i].name);
            j -= spots[i].time;
            i--;
        }
    }
    
    return 0;
}