すべてのパーツの重さの合計を \(S\) とします。

はじめ、すべてのパーツを体に取り付けて、いくつかのパーツを頭に移動させることを考えます。

すると、次のような問題が解ければよいことがわかります。

\(i\) 番目の品物は、重さが \(W _ i\) で、価値が \(V_ i=H _ i-B _ i\) です。 重さの合計が \(\left\lfloor\dfrac S2\right\rfloor\) 以下であるように品物をいくつか選んだときの、価値の合計としてありえる最大値を求めてください。

これは典型的なナップサック問題で、動的計画法を用いて時間計算量 \(O(NS)\) で解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>

int main() {
    using namespace std;
    int N;
    cin >> N;
    vector<long> dp{0}, prev;
    for (int n = 0; n < N; ++n) {
        int w, h, b;
        cin >> w >> h >> b;
        swap(dp, prev);
        const auto M = size(prev);
        dp.resize(M + w);
        for (int i = 0; i < M; ++i) {
            dp[i] = max(dp[i], prev[i] + h); // 頭に取り付ける
            dp[i + w] = max(dp[i + w], prev[i] + b); // 体に取り付ける
        }
    }
    cout << ranges::max(dp | views::drop(size(dp) / 2)) << endl;
    return 0;
}