编辑代码

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

#define MAX_NAME_LENGTH 50

int max(int a, int b) {
    return (a > b) ? a : b;
}

void optimizeTravel(int days, int scores[], int times[], char names[][MAX_NAME_LENGTH], int numSpots) {
    int dp[numSpots + 1][days + 1];
    int path[numSpots + 1][days + 1][numSpots + 1];

    for (int i = 0; i <= numSpots; i++) {
        for (int j = 0; j <= days; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (times[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                int includeScore = dp[i - 1][j - times[i - 1]] + scores[i - 1];
                int excludeScore = dp[i - 1][j];

                if (includeScore > excludeScore) {
                    dp[i][j] = includeScore;
                    for (int k = 0; k < i; k++) {
                        path[i][j][k] = path[i - 1][j - times[i - 1]][k];
                    }
                    path[i][j][i - 1] = 1;
                } else {
                    dp[i][j] = excludeScore;
                    for (int k = 0; k < i; k++) {
                        path[i][j][k] = path[i - 1][j][k];
                    }
                }
            }
        }
    }

    printf("最大评分为：%d\n", dp[numSpots][days]);
    printf("旅游路线为：\n");
    int remainingDays = days;
    for (int i = numSpots; i >= 1; i--) {
        if (path[numSpots][days][i - 1] == 1) {
            printf("景点：%s（评分：%d，天数：%d）\n", names[i - 1], scores[i - 1], times[i - 1]);
            remainingDays -= times[i - 1];
        }
    }
}

int main() {
    int days = 4;
    int scores[] = {7, 8, 9, 6};
    int times[] = {1, 2, 3, 1};
    char names[][MAX_NAME_LENGTH] = {"故宫", "颐和园", "长城", "天坛"};
    int numSpots = sizeof(scores) / sizeof(scores[0]);

    optimizeTravel(days, scores, times, names, numSpots);

    return 0;
}