また、制約条件(第 2 式)は、全ての部品の重さの合計を $S = \sum_{i=1}^{N} W_i$ とすると、 $\sum_{j \in \mathrm{body}} W_j = S - \sum_{i \in \mathrm{head}} W_i$ であるから、 $\sum_{i \in \mathrm{head}} W_i \leq \frac{1}{2} S$ と書ける。

したがって、冒頭の定式化は以下のように書き換えられる。

\begin{align*} \mathrm{Maximize:} \quad & \sum_{i=1}^{N} B_i + \sum_{i \in \mathrm{head}} (H_i - B_i) \\ \mathrm{s.t.} \quad & \sum_{i \in \mathrm{head}} W_i \leq \frac{1}{2} S \end{align*}

なお、第 1 式の $\sum_{i=1}^{N} B_i$ は定数なので、実質的には $\sum_{i \in \mathrm{head}} (H_i - B_i)$ を最大化すればよいことになる。

これは、重さ $W_i$ 、価値 $H_i - B_i$ の品物を重さの合計が $\frac{1}{2} S$ 以下になるように選んで価値の合計を最大化する、すなわち典型的なナップザック問題に帰着できる。

あとは、動的計画法でこの問題を解けばよい。

二次元 DP テーブルを以下のように定義する。

$\mathrm{dp}_{i, v} := i$ 番目までの部品までを考えたときに、頭に取り付けた部品の重さの合計が $v$ になるように選んだときの $\underset{i}{\sum} (H_i - B_i)$ の合計の最大値 $(0 \leq i \leq N, 0 \leq v \leq \frac{1}{2} S)$

初期値は $\mathrm{dp}_{0, 0} = 0$ 、その他を $\mathrm{dp}_{0, v} = -\infty$ とする。

漸化式は以下のようになる。

\mathrm{dp}_{i, v} = \begin{cases} \mathrm{dp}_{i-1, v} & (v < W_{i}) \\ \max(\mathrm{dp}_{i-1, v}, \mathrm{dp}_{i-1, v - W_{i}} + (H_{i} - B_{i})) & (v \geq W_{i}) \end{cases}

※ 前者は $i$ 番目の部品を頭に取り付けない場合、後者は頭に取り付ける場合

答えは、 $\underset{0 \leq v \leq \frac{1}{2} S}{\max} \mathrm{dp}_{N, v} + \sum_{i=1}^{N} B_i$ である。

定数部分を加えるのを忘れないように注意すること。

実装例

横着して DP テーブルのサイズを $N \times S$ とすると MLE になる。

実装例では、 $S$ の定義を $S = \frac{1}{2} \sum_{i=1}^{N} W_i$ としていることに注意。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr long long INFL = 1e+18;
7. 
8.using ll = long long;
9. 
10.template <typename T>
11.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N;
18.    cin >> N;
19.    vector<ll> W(N), H(N), B(N);
20.    rep(i, 0, N) cin >> W[i] >> H[i] >> B[i];
21. 
22.    ll sum_W = 0, sum_B = 0;
23.    rep(i, 0, N)
24.    {
25.        sum_W += W[i];
26.        sum_B += B[i];
27.    }
28.    ll S = sum_W / 2;
29. 
30.    vector<vector<ll>> dp(N + 1, vector<ll>(S + 1, -INFL));
31.    dp[0][0] = 0;
32.    rep(i, 1, N + 1)
33.    {
34.        rep(v, 0, S + 1)
35.        {
36.            dp[i][v] = dp[i - 1][v];
37.            if (v >= W[i - 1])
38.                chmax(dp[i][v], dp[i - 1][v - W[i - 1]] + (H[i - 1] - B[i - 1]));
39.        }
40.    }
41. 
42.    ll ans = -INFL;
43.    rep(v, 0, S + 1) chmax(ans, dp[N][v]);
44. 
45.    cout << ans + sum_B << endl;
46. 
47.    return 0;
48.}