#include <iostream>
#include <vector>
#include <cmath>
class Goal {
public:
std::string name;
int day;
int score;
Goal(std::string n, int d, int s) {
name = n;
day = d;
score = s;
}
};
void maxBackpackByValue(int num, std::vector<Goal>& goals) {
int n = goals.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(num + 1, 0));
std::vector<std::vector<bool>> selected(n + 1, std::vector<bool>(num + 1, false));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= num; j++) {
if (goals[i - 1].day <= j) {
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - goals[i - 1].day] + goals[i - 1].score);
if (dp[i][j] > dp[i - 1][j]) {
selected[i][j] = true;
}
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int i = n;
int j = num;
std::cout << "旅游行程最优化路线:" << std::endl;
while (i > 0 && j > 0) {
if (selected[i][j]) {
std::cout << goals[i - 1].name << std::endl;
j -= goals[i - 1].day;
}
i--;
}
std::cout << "总评分:" << dp[n][num] << std::endl;
}
int main() {
std::vector<Goal> goals = {
Goal("故宫", 1, 7),
Goal("颐和园", 2, 8),
Goal("长城", 3, 9),
Goal("天坛", 1, 6)
};
maxBackpackByValue(4, goals);
return 0;
}