题解 | 毕业bg

解法一：背包问题变形
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//经典背包问题加了个时间限制
struct BG {
    int h; // 快乐度
    int l; // 持续时间
    int t; // 发起人离校时间
};

bool compare(const BG& a, const BG& b) {
    return a.t < b.t; // 按离校时间升序排序
}

int main() {
    int N;
    while (cin >> N && N >= 0) { // 处理多个测试用例
        vector<BG> bgs(N);
        for (int i = 0; i < N; i++) {
            cin >> bgs[i].h >> bgs[i].l >> bgs[i].t;
        }

        // 按离校时间升序排序（此处为变化的地方）
        sort(bgs.begin(), bgs.end(), compare);

        // 动态规划
        int maxTime = bgs.back().t; // 最大时间
        vector<vector<int>> dp(N + 1, vector<int>(maxTime + 1, 0)); // dp[i][j]

        for (int i = 1; i <= N; i++) {
            int h = bgs[i - 1].h, l = bgs[i - 1].l, t = bgs[i - 1].t;
            for (int j = 0; j <= maxTime; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选择第 i 个 BG
                if (j >= l && j <= t) { // 选择第 i 个 BG（此处为变化）
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - l] + h);
                }
            }
        }

        // 找到最大快乐度
        int maxHappiness = 0;
        for (int j = 0; j <= maxTime; j++) {
            maxHappiness = max(maxHappiness, dp[N][j]);
        }
        cout << maxHappiness << endl;
    }
    return 0;
}



解法二：dfs剪枝
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct BG {
    int h; // 快乐度
    int l; // 持续时间
    int t; // 发起人离校时间
};

bool compare(const BG& a, const BG& b) {
    return a.t < b.t; // 按离校时间升序排序
}

int maxHappiness = 0; // 最大快乐度

// DFS 搜索
void dfs(const vector<BG>& bgs, int index, int currentTime, int currentHappiness) {
    // 更新最大快乐度
    if (currentHappiness > maxHappiness) {
        maxHappiness = currentHappiness;
    }

    // 剪枝：如果剩余 BG 的最大可能快乐度加上当前快乐度仍然小于 maxHappiness，则剪枝
    int remainingHappiness = 0;
    for (int i = index; i < bgs.size(); i++) {
        remainingHappiness += bgs[i].h;
    }
    if (currentHappiness + remainingHappiness <= maxHappiness) {
        return;
    }

    // 枚举每个 BG
    for (int i = index; i < bgs.size(); i++) {
        if (currentTime + bgs[i].l <= bgs[i].t) { // 时间限制剪枝
            dfs(bgs, i + 1, currentTime + bgs[i].l, currentHappiness + bgs[i].h);
        }
    }
}

int main() {
    int N;
    while (cin >> N && N >= 0) { // 处理多个测试用例
        vector<BG> bgs(N);
        for (int i = 0; i < N; i++) {
            cin >> bgs[i].h >> bgs[i].l >> bgs[i].t;
        }

        // 按离校时间升序排序
        sort(bgs.begin(), bgs.end(), compare);

        // 初始化
        maxHappiness = 0;

        // DFS 搜索
        dfs(bgs, 0, 0, 0);

        // 输出结果
        cout << maxHappiness << endl;
    }
    return 0;
}