编辑代码

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

#define MAX_NAME_LENGTH 50

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

void optimize_travel(int days, int scores[], int times[], char names[][MAX_NAME_LENGTH], int n) {
    int dp[n + 1][days + 1];
    int path[n + 1][days + 1][n + 1];
    
    for (int i = 0; i <= n; 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 include_score = dp[i - 1][j - times[i - 1]] + scores[i - 1];
                int exclude_score = dp[i - 1][j];
                
                if (include_score > exclude_score) {
                    dp[i][j] = include_score;
                    for (int k = 0; k < i - 1; k++) {
                        path[i][j][k] = path[i - 1][j - times[i - 1]][k];
                    }
                    path[i][j][i - 1] = 1;
                } else {
                    dp[i][j] = exclude_score;
                    for (int k = 0; k < i - 1; k++) {
                        path[i][j][k] = path[i - 1][j][k];
                    }
                }
            }
        }
    }
    
    printf("最大评分为：%d\n", dp[n][days]);
    printf("旅游路线为：\n");
    int remaining_days = days;
    for (int i = n; i >= 1; i--) {
        if (path[n][days][i - 1] == 1) {
            printf("景点：%s（评分：%d，天数：%d）\n", names[i - 1], scores[i - 1], times[i - 1]);
            remaining_days -= 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 n = sizeof(scores) / sizeof(scores[0]);
    
    optimize_travel(days, scores, times, names, n);
    
    return 0;
}