编辑代码

#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;
}