编辑代码

#include <stdio.h>
#define MAX(x,y) ((x) > (y) ? (x) : (y))

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

void findMaxScore(Spot spots[], int numSpots, int maxTime) {
    int dp[numSpots+1][maxTime+1];
    int chosen[numSpots+1][maxTime+1];

    for (int i = 0; i <= numSpots; i++) {
        for (int j = 0; j <= maxTime; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
                chosen[i][j] = 0;
            } else if (spots[i-1].time <= j) {
                int scoreWithSpot = spots[i-1].score + dp[i-1][j-spots[i-1].time];
                int scoreWithoutSpot = dp[i-1][j];
                if (scoreWithSpot >= scoreWithoutSpot) {
                    dp[i][j] = scoreWithSpot;
                    chosen[i][j] = 1;
                } else {
                    dp[i][j] = scoreWithoutSpot;
                    chosen[i][j] = 0;
                }
            } else {
                dp[i][j] = dp[i-1][j];
                chosen[i][j] = 0;
            }
        }
    }

    printf("选择的景点：\n");
    int i = numSpots, j = maxTime;
    while (i > 0 && j > 0) {
        if (chosen[i][j]) {
            printf("%s\n", spots[i-1].name);
            j -= spots[i-1].time;
        }
        i--;
    }

    printf("\n最大价值：%d\n", dp[numSpots][maxTime]);
}

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

    findMaxScore(spots, numSpots, maxTime);

    return 0;
}