编辑代码

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

#define MAX_SPOTS 100
#define MAX_TIME  32

typedef struct {
    char name[32];
    int time;
    int score;
} spot_t;

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

int dp[MAX_SPOTS+1][MAX_TIME+1];

int main() {
    // 按评分排序
    for (int i = 0; i < num_spots; i++) {
        for (int j = i+1; j < num_spots; j++) {
            if (spots[i].score < spots[j].score) {
                spot_t tmp = spots[i];
                spots[i] = spots[j];
                spots[j] = tmp;
            }
        }
    }

    // 动态规划
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= num_spots; i++) {
        for (int j = 1; j <= MAX_TIME * 8; j++) {
            if (j < spots[i-1].time * 8) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
                if (dp[i-1][j-spots[i-1].time*8] + spots[i-1].score > dp[i][j]) {
                    dp[i][j] = dp[i-1][j-spots[i-1].time*8] + spots[i-1].score;
                }
            }
        }
    }

    // 输出结果
    printf("去旅游的景点有：\n");
    int time_left = MAX_TIME * 8;
    for (int i = num_spots; i > 0; i--) {
        if (dp[i][time_left] > dp[i-1][time_left]) {
            printf("%s（%d天）\n", spots[i-1].name, spots[i-1].time);
            time_left -= spots[i-1].time * 8;
        }
    }
    printf("总评分：%d\n", dp[num_spots][MAX_TIME*8]);

    return 0;
}