C++で解く「収益性のある計画」問題 ― 動的計画法による効率的なアプローチ

この記事では、「収益性のある計画（Profitable Schemes）」と呼ばれる動的計画法の定番問題を、C++を使って解く方法を詳しく解説します。

問題の概要

G人からなるギャングと、彼らが実行できるさまざまな「犯罪（仕事）」のリストがあるとします。i番目の犯罪は profit[i] の利益を生み出し、group[i] 人のメンバーを必要とします。

ここで重要な制約として、1人のメンバーは複数の犯罪に同時に参加できないというものがあります。

「収益性のある計画」とは、以下の2つの条件を満たす犯罪の部分集合として定義されます。

• その部分集合から得られる合計利益が P以上 である
• その部分集合に参加するメンバーの総数が G以下 である

このような計画が何通り存在するかを求めるのが本問題です。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

入力例

G = 5、P = 3、group = [2, 2]、profit = [2, 3] の場合を考えてみましょう。

• 1つ目の犯罪：メンバー2人で利益2
• 2つ目の犯罪：メンバー2人で利益3
• 両方の犯罪を実行：メンバー4人（≤5）で利益5（≥3）→ 条件を満たす
• 2つ目の犯罪のみ実行：メンバー2人（≤5）で利益3（≥3）→ 条件を満たす

したがって、答えは 2 となります。

解法のアプローチ

この問題はナップサック問題の変形であり、2次元の動的計画法（DP）で解くことができます。

dp[i][j] を「i人のメンバーを使い、利益が j 以上になる組み合わせの数」と定義します。ただし、利益は P を超えた時点で条件を満たすため、利益の次元は P に制限（キャップ）しても問題ありません。

アルゴリズムの手順

1. ret := 0 と初期化する
2. サイズ (G + 1) × (P + 1) の2次元配列 dp を定義し、すべて0で初期化する
3. dp[0][0] := 1 とする（何も選ばない状態が1通り）
4. 各犯罪 k について、p := profit[k]、g := group[k] とし、以下を繰り返す：
   • i を G − g から 0 まで降順でループする
   • j を P から 0 まで降順でループし、次の更新を行う：
     dp[i + g][min(P, j + p)] += dp[i][j]
     その後、剰余 m を取る
5. 最後に、i = 0 から G までの dp[i][P] の総和を計算し、ret に加算していく
6. ret を返す

なぜ降順でループするのか？

各犯罪は一度しか使えないため、i と j を降順に回すことで、同じ犯罪を同じ遷移内で二重に数えてしまうことを防げます。これは典型的な0/1ナップサック型DPのテクニックです。また、利益を min(P, j + p) で切り詰めることで、P以上の利益をすべて同じ状態にまとめ、配列サイズを抑えています。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

class Solution {
public:
    int profitableSchemes(int G, int P, vector<int> &group, vector<int> &profit) {
        int ret = 0;
        vector<vector<int>> dp(G + 1, vector<int>(P + 1));
        dp[0][0] = 1;
        
        for (int k = 0; k < group.size(); k++) {
            int p = profit[k];
            int g = group[k];
            for (int i = G - g; i >= 0; i--) {
                for (int j = P; j >= 0; j--) {
                    dp[i + g][min(P, j + p)] += dp[i][j];
                    dp[i + g][min(P, j + p)] %= MOD;
                }
            }
        }
        
        for (int i = 0; i <= G; i++) {
            ret += dp[i][P];
            ret %= MOD;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 2}, v1 = {2, 3};
    cout << ob.profitableSchemes(5, 3, v, v1);
    return 0;
}

入力と出力

入力

5, 3, [2,2], [2,3]

出力

2

計算量について

このアルゴリズムの時間計算量は O(N × G × P)、空間計算量は O(G × P) です（N は犯罪の数）。制約が n ≤ 100 程度の規模であれば十分に高速に動作します。さらに、1次元配列を使い回すことで空間を削減することも可能ですが、まずは2次元DPでロジックを理解するのがおすすめです。