编辑代码

#include <stdio.h>

#define N 4  // 景点数量
#define T 4  // 总时间

// 定义景点结构体
typedef struct {
    char name[20];  // 景点名称
    int time;       // 需要的时间
    int score;      // 评分
} Spot;

// 初始化景点数据
void initSpots(Spot spots[]) {
    strcpy(spots[0].name, "故宫");
    spots[0].time = 1;
    spots[0].score = 7;

    strcpy(spots[1].name, "颐和园");
    spots[1].time = 2;
    spots[1].score = 8;

    strcpy(spots[2].name, "长城");
    spots[2].time = 3;
    spots[2].score = 9;

    strcpy(spots[3].name, "天坛");
    spots[3].time = 1;
    spots[3].score = 6;
}

// 输出选择的景点
int printSelectedSpots(int dp[N+1][T+1], Spot spots[], int *maxValue) {
    int i = N;
    int j = T;

    int maxScore = dp[N][T];  // 最大价值

    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i-1][j]) {
            printf("经过%s\n", spots[i-1].name);
            j -= spots[i-1].time;
        }
        i--;
    }

    *maxValue = maxScore;
}

int main() {
    Spot spots[N];  // 存储景点信息

    initSpots(spots);  // 初始化景点数据

    int dp[N+1][T+1];  // 动态规划表
    memset(dp, 0, sizeof(dp));  // 初始化为0

    // 计算最大价值
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= T; j++) {
            if (j >= spots[i-1].time) {
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-spots[i-1].time] + spots[i-1].score) ? dp[i-1][j] : (dp[i-1][j-spots[i-1].time] + spots[i-1].score);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    printf("路途经过那些景点能够获得最大价值：\n");
    int maxValue;
    printSelectedSpots(dp, spots, &maxValue);
    printf("最大价值为：%d\n", maxValue);

    return 0;
}