// 定义最大景点数量和最大旅行天数
int max(int a, int b) {
return (a > b) ? a : b;
}
// 打印最优旅行方案
void tour(int sights[MAX_SIGHTS][2], int days) {
int dp[MAX_SIGHTS + 1][MAX_DAYS + 1];// 定义了一个二维数组dp,用于保存动态规划的结果
int i, j;
// 初始化动态规划数组
for (i = 0; i <= MAX_SIGHTS; i++) {
for (j = 0; j <= MAX_DAYS; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (sights[i - 1][0] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - sights[i - 1][0]] + sights[i - 1][1]);
}
}
// 打印最优旅行价值和选中的景点
printf("最优旅行价值:%d\n", dp[MAX_SIGHTS][days]);
printf("选中的景点:\n");
i = MAX_SIGHTS;
j = days;
//根据动态规划的结果,回溯选中的景点
while (i > 0 && j > 0) {
if (dp[i][j] != dp[i - 1][j]) {
printf("景点%d\n", i);
j -= sights[i - 1][0];
}
i--;
}
}
int main() {
int sights[MAX_SIGHTS][2] = {{1, 7}, {2, 8}, {3, 9}, {1, 6}};
int days = 4;
tour(sights, days);
return 0;
}