编辑代码

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

// 定义景点结构体
struct Attraction {
    char name[50];
    int time;
    int score;
};

// 旅游行程最优化问题求解函数
int travelOptimization(int tripDuration, struct Attraction *attractions, int attractionCount) {
    
    // 计算所有景点中最小的时间
    int minTime = attractions[0].time;

    for (int i = 1; i < attractionCount; ++i)
    {
        int curTime = attractions[i].time;
        if (curTime < minTime) {
            minTime = curTime;
        }
    }

    // 如果旅行时间小于最小景点时间，无法游览任何景点
    if (tripDuration < minTime) {
        printf("旅行时间 %d 小于所有景点的最小时间 %d\n", tripDuration, minTime);
        return -1;
    }

    // 创建表格，行表示景点，列表示旅行能容纳的时间
    int timeCount = tripDuration + 1;
    int** dpArray = (int**)malloc(attractionCount * sizeof(int*));
    for (int i = 0; i < attractionCount; ++i) {
        dpArray[i] = (int*)malloc(timeCount * sizeof(int));
    }

    // 填充表格
    for (int i = 0; i < attractionCount; ++i)
    {
        // 记录游览景点所需的时间和评分
        int curTime = attractions[i].time;
        int curScore = attractions[i].score;
        for (int t = minTime; t < timeCount; ++t)
        {
            // 记录不游览当前景点的情况下，游览景点能够达到的最大评分
            int preTotalScore = 0;

            if (i > 0) {
                preTotalScore = dpArray[i - 1][t];
            }
            
            // 记录游览当前景点的情况下，游览景点能够达到的最大评分
            int curTotalScore = 0;

            // 如果当前景点能够游览，记录下景点的评分
            if (t >= curTime) {
                curTotalScore = curScore;
            }
            // 如果游览当前景点后旅行还能游览其它景点，且确实还有其它景点，加上剩余的小行程能够游览景点的最大评分
            if (t > curTime && i > 0) {
                curTotalScore += dpArray[i-1][t - curTime];
            }
      
            // 找出游览当前景点和不游览当前景点情况下，游览景点的旅行能够达到的最大评分
            int maxTotalScore = preTotalScore;

            if (maxTotalScore < curTotalScore) {
                maxTotalScore = curTotalScore;
            }

            // 记录下游览当前景点后，能够游览t天的旅行能够游览景点的最大评分
            dpArray[i][t] = maxTotalScore;

        }    
    }

    // 记录下最终的最大评分
    int maxScore = dpArray[attractionCount - 1][timeCount - 1];

    // 打印选择的景点
    printf("选择去");
    int remainingTime = tripDuration;
    for (int i = attractionCount - 1; i >= 0; --i) {
        if (i > 0 && dpArray[i][remainingTime] != dpArray[i - 1][remainingTime]) {
            // The attraction at index i was selected
            printf("%s ", attractions[i].name);
            remainingTime -= attractions[i].time;
        }
    }
    printf("\n");

    // 释放动态分配的内存
    for (int i = 0; i < attractionCount; ++i) {
        free(dpArray[i]);
    }
    free(dpArray);
    
    return maxScore;
}

int main() {
    // 旅行时间
    int tripDuration = 4;
    // 景点数组
    struct Attraction attractions[] = {     
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };
    // 景点数量
    int attractionCount = sizeof(attractions) / sizeof(struct Attraction);
    // 最大评分
    int maxScore = 0;

    // 求解旅游行程最优化问题
    maxScore = travelOptimization(tripDuration, attractions, attractionCount);

    // 输出结果
    if (maxScore > 0) {
        printf("旅行能够获得的最大评分是 %d\n", maxScore);
    }    
    return 0;
}