#include <iostream>
#include <algorithm>
void travelOptimization(int time[], int score[], int total) {
int n = sizeof(time) / sizeof(time[0]);
int dp[n + 1][total + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= total; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (j >= time[i - 1]) {
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - time[i - 1]] + score[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int max = dp[n][total];
std::cout << "最大价值为:" << max << "分" << std::endl;
std::cout << "可选择的景点有:" << std::endl;
int daysLeft = total;
for (int i = n; i > 0 && max > 0; i--) {
if (max != dp[i - 1][daysLeft]) {
std::cout << "景点" << i << "(时间:" << time[i - 1] << "天,评分:" << score[i - 1] << "分)" << std::endl;
max -= score[i - 1];
daysLeft -= time[i - 1];
}
}
}
int main() {
int time[] = {1, 2, 3, 1};
int score[] = {7, 8, 9, 6};
int total = 4;
travelOptimization(time, score, total);
return 0;
}