void travel_plan(int days, int n, int time[], int score[], char* names[]) {
int dp[5][5] = {0};
for (int i = 0; i < n; i++) {
for (int j = 0; j <= days; j++) {
if (j < time[i]) {
dp[i+1][j] = dp[i][j];
} else {
dp[i+1][j] = MAX(dp[i][j], dp[i][j-time[i]] + score[i]);
}
}
}
printf("最大价值为:%d\n", dp[n][days]);
printf("去以下景点:\n");
int v = days;
for (int i = n; i > 0; i--) {
if (dp[i][v] != dp[i-1][v]) {
printf("%s ", names[i-1]);
v -= time[i-1];
}
}
}
int main() {
int days = 4;
int n = 4;
int time[4] = {1, 2, 3, 1};
int score[4] = {7, 8, 9, 6};
char* names[4] = { "故宫", "颐和园", "长城", "天坛"};
travel_plan(days, n, time, score, names);
return 0;
}