编辑代码

#include <stdio.h>

typedef struct {
    char *name;
    int time;
    int score;
} Spot;


// 动态规划
void maxTour(Spot spots[], int days, int num_spots) {
    int dp[4] = {0};
    int chosen[4] = {-1}; 
    int i, j;
    for (i = 0; i < num_spots; i++) {
        for (j = days; j >= spots[i].time; j--) {
            if (dp[j] < dp[j - spots[i].time] + spots[i].score) {
                dp[j] = dp[j - spots[i].time] + spots[i].score;
                chosen[j] = i;
            }
        }
    }
    printf("最大价值: %d\n", dp[days]);
    printf("景点有: ");
    for (i = days; i > 0 && chosen[i] != -1; ) {
        printf("%s ", spots[chosen[i]].name);
        i -= spots[chosen[i]].time;
    }
}

int main() {

    Spot spots[4] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };
    maxTour(spots,4,4);
    return 0;
}