問題概要

n 個の要素があり、それぞれに整数値の属性 a と b が割り当てられています。いくつかの要素を選択して、選ばれた要素の a 属性の合計 と b 属性の合計 の総和を最大化したいと考えます。ただし、以下の条件を満たす必要があります：

• a 属性の合計 ≥ 0
• b 属性の合計 ≥ 0

この条件下で、(aの合計) + (bの合計) を最大にするプログラムを作成します。

アプローチ

この問題は、典型的なナップサック問題の変形として捉えることができます。一方の属性（例えば a）を「重さ」とみなし、もう一方の属性（b）を「価値」とみなすことで、DP 配列を用いて状態を管理できます。

しかし、a の値が負になる可能性があるため、通常の配列インデックスでは扱えません。そこで、オフセットを導入して負のインデックスを表現できるようにします。

オフセット付き DP の設計

• 最大で n = 400、各 |a| ≤ 1000 であるため、a の合計は最大で -400,000 から +400,000 の範囲を取り得ます。
• したがって、配列サイズを 800,001 とし、400,000 を「ゼロ点」として使用します。
• つまり、dp[i] は、「a 属性の合計が i - 400000」となるような選び方における、b 属性の最大合計値 を表します。

初期化と遷移

初期状態として、何も選ばない場合は a 合計 = 0、b 合計 = 0 なので：

dp[400000] = 0;  // オフセットを加味

他の状態は非常に小さい値（マイナス無限大）で初期化します。

各要素について、以下のように DP 配列を更新します：

• a[i] ≥ 0 の場合：通常の 0-1 ナップザックと同じく、大きいインデックスから小さい方向へ 更新します。
• a[i] < 0 の場合：負の「重さ」を持つアイテムのため、小さいインデックスから大きい方向へ 更新することで、同じアイテムを複数回使わないようにします。

コード実装

#include <bits/stdc++.h>
using namespace std;

const int OFFSET = 400000;
const int MAX_SIZE = 800001;
const int NEG_INF = -1e9;

int n;
int a[405], b[405];
int dp[MAX_SIZE];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }

    fill(dp, dp + MAX_SIZE, NEG_INF);
    dp[OFFSET] = 0;

    for (int i = 1; i <= n; ++i) {
        if (a[i] >= 0) {
            // 正の重み → 後ろから更新
            for (int j = MAX_SIZE - 1; j >= a[i]; --j) {
                if (dp[j - a[i]] != NEG_INF) {
                    dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
                }
            }
        } else {
            // 負の重み → 前から更新
            for (int j = 0; j <= MAX_SIZE - 1 + a[i]; ++j) {
                if (dp[j - a[i]] != NEG_INF) {
                    dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
                }
            }
        }
    }

    int result = 0;
    for (int j = OFFSET; j < MAX_SIZE; ++j) {
        if (dp[j] >= 0) {
            int totalA = j - OFFSET;
            int totalB = dp[j];
            result = max(result, totalA + totalB);
        }
    }

    cout << result << endl;
    return 0;
}

最終的な答えは、j ≥ OFFSET かつ dp[j] ≥ 0 を満たすすべての状態において、(j - OFFSET) + dp[j] の最大値です。