#include <stdio.h>
#include <string.h>
struct Sight {
char name[20];
int daysRequired;
int rating;
};
void findMaxValue(struct Sight sights[], int n, int days) {
int dp[days + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
for (int j = days; j >= sights[i].daysRequired; j--) {
dp[j] = dp[j] > dp[j - sights[i].daysRequired] + sights[i].rating ? dp[j] :
dp[j - sights[i].daysRequired] + sights[i].rating;
}
}
printf("最大价值: %d\n", dp[days]);
printf("旅行路线:\n");
int remainDays = days;
for (int i = n - 1; i >= 0; i--) {
if (remainDays >= sights[i].daysRequired && dp[remainDays] ==
dp[remainDays - sights[i].daysRequired] + sights[i].rating)
{
printf("%s\n", sights[i].name);
remainDays -= sights[i].daysRequired;
}
}
}
int main() {
struct Sight sights[] = {
{"故宫", 1, 7},
{"颐和园", 2, 8},
{"长城", 3, 9},
{"天坛", 1, 6}
};
int n = sizeof(sights) / sizeof(sights[0]);
int days = 4;
findMaxValue(sights, n, days);
return 0;
}