制限時間T以内で解ける問題の組み合わせの最長時間を求めるC++プログラム

N個の要素を持つ配列Aと、ある数値Tがあるとします。Amalはプログラミングコンテストへの参加を考えています。コンテストの制限時間はT分間で、全部でN問の問題が出題されます。i番目の問題を解くにはA[i]分の時間がかかります。彼はN問の中から0問以上を選んで解きますが、選んだ問題を解くのにかかる合計時間はT分を超えてはなりません。このとき、選択した問題の合計時間として実現できる最長の時間を求めます。

たとえば、入力がT = 17、A = [2, 3, 5, 7, 11]である場合、出力は17になります。これは、最初の4問を選ぶと2 + 3 + 5 + 7 = 17分となり、これがT分を超えない範囲で到達できる最長の時間だからです。

アプローチ:半分全列挙(Meet in the Middle)

この問題は部分和問題の一種です。すべての問題の組み合わせを素朴に列挙すると2^N通りの計算が必要となり、Nが大きくなると現実的な時間で処理できません。そこで「半分全列挙」と呼ばれる手法を用います。配列を前半と後半の2つに分割し、それぞれの部分集合の合計値をすべて求めておき、後から両者を組み合わせることで、計算量をO(2^N/2)程度まで削減できます。

手順

この問題を解くために、以下の手順を実行します。

n := Aのサイズ
サイズ (n / 2) の配列 b と、サイズ (n - n/2) の配列 c を定義
for i := 0 から n / 2 未満まで、i を 1 ずつ増やしながら繰り返す:
    b[i] := A[i]
for i := n / 2 から n 未満まで、i を 1 ずつ増やしながら繰り返す:
    c[i - n / 2] := A[i]
配列 B, C を定義
for bit := 0 から 2^(n/2) 未満まで、bit を 1 ずつ増やしながら繰り返す:
    p := 0
    for i := 0 から n / 2 未満まで、i を 1 ずつ増やしながら繰り返す:
        もし bit AND 2^i が 0 以外なら:
            p := p + b[i]
    p を B の末尾に追加
for bit := 0 から 2^(n - n/2) 未満まで、bit を 1 ずつ増やしながら繰り返す:
    p := 0
    for i := 0 から n - n / 2 未満まで、i を 1 ずつ増やしながら繰り返す:
        もし bit AND 2^i が 0 以外なら:
            p := p + c[i]
    p を C の末尾に追加
mx := 0
配列 C をソート
for i := 0 から Bのサイズ未満まで、i を 1 ずつ増やしながら繰り返す:
    もし t - B[i] < 0 なら:
        処理をスキップして次の反復へ
    itr := C 内で (t - B[i]) より大きい最初の要素を指すイテレータ
    itr を 1 つ戻す
    mx := mx と (itr + B[i]) の最大値
mx を返す

手順のポイントを整理すると次のとおりです。

• 配列Aを前半bと後半cに分割します。
• ビット全探索により、それぞれの部分集合の合計値をBとCに格納します。
• Cをあらかじめソートしておけば、Bの各要素に対して二分探索(upper_bound)を使い、残り時間内に収まる最大の値を効率的に見つけられます。

実装例

理解を深めるために、以下のC++による実装例を見てみましょう。

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

int solve(int t, vector<int> A){
    int n = A.size();
    vector<int> b(n / 2), c(n - n / 2);
    for (int i = 0; i < n / 2; i++)
        b[i] = A[i];
    for (int i = n / 2; i < n; i++)
        c[i - n / 2] = A[i];
    vector<int> B, C;
    for (int bit = 0; bit < (1 << (n / 2)); bit++){
        int p = 0;
        for (int i = 0; i < n / 2; i++){
            if (bit & (1 << i))
                p += b[i];
        }
        B.push_back(p);
    }
    for (int bit = 0; bit < (1 << (n - n / 2)); bit++){
        int p = 0;
        for (int i = 0; i < n - n / 2; i++){
            if (bit & (1 << i))
                p += c[i];
        }
        C.push_back(p);
    }
    int mx = 0;
    sort(C.begin(), C.end());
    for (int i = 0; i < B.size(); i++){
        if (t - B[i] < 0)
            continue;
        auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
        itr--;
        mx = max(mx, *itr + B[i]);
    }
    return mx;
}
int main(){
    int T = 17;
    vector<int> A = { 2, 3, 5, 7, 11 };
    cout << solve(T, A) << endl;
}

入力

17, { 2, 3, 5, 7, 11 }

出力

17