Algorithm Deep Dive

部分和問題と
Meet-in-the-Middle法

343億通りの組み合わせを40万通りに削減し、1秒で最適解を見つけるアルゴリズムの解説。

343億

全探索の計算量

40万

最適化後の計算量

87,381倍

高速化

問題設定

実際の依頼内容

35件の配当金データから、合計が目標金額（7,240,268円）を超えない範囲で、最大限その金額に近づける組み合わせを見つける。

課題

全件合計は7,331,370円で、目標を91,102円超過している。どの項目を除外すべきか？

なぜ難しいのか

35件のデータがあるとき、各項目は「計上する」か「しない」かの2択。

// 組み合わせの数
項目1: 計上 or 除外 → 2通り
項目2: 計上 or 除外 → 2通り
項目3: 計上 or 除外 → 2通り
...
項目35: 計上 or 除外 → 2通り

全組み合わせ = 2 × 2 × 2 × ... × 2（35回）
            = 2^35
            = 34,359,738,368 通り（約343億）

計算時間の目安

1秒に100万通り処理できるとしても、約9.5時間かかる。

Meet-in-the-Middle法

核心：半分に分けて、後で合流

「全部を一度に処理する」のではなく、「半分ずつ処理して組み合わせる」という発想。

データ分割のイメージ

従来

35件を一気に処理 → 2³⁵ = 343億通り

↓

新発想

前半17件 → 2¹⁷ = 13万通り

後半18件 → 2¹⁸ = 26万通り

効果

343億通り → 40万通り = 約87,000倍の高速化

アルゴリズムの3ステップ

データを2分割

35件のデータを前半17件・後半18件に分ける

各グループで可能な合計を全列挙

前半グループで作れる全ての合計値、後半グループで作れる全ての合計値をそれぞれ計算

最適な組み合わせを二分探索で発見

前半の各合計に対して、「後半から足しても目標を超えない最大値」を高速に検索

なぜ「半分」が魔法なのか

n件のデータの場合

全探索:           2^n
Meet-in-Middle:   2^(n/2) + 2^(n/2) = 2 × 2^(n/2)

// 高速化の比率
比率 = 2^n / (2 × 2^(n/2))
     = 2^(n/2) / 2
     = 2^(n/2 - 1)

件数	全探索	Meet-in-Middle	高速化倍率
20件	100万	2,048	512倍
30件	10億	65,536	16,384倍
35件	343億	393,216	87,381倍
40件	1兆	約200万	524,288倍

具体例で理解する

簡単な例：6件のデータで目標100以下の最大を探す

データ: [10, 25, 30, 15, 20, 35]
目標: 100以下で最大

Step 1: 半分に分ける

前半グループ: [10, 25, 30]
後半グループ: [15, 20, 35]

Step 2: 各グループの可能な合計を全列挙

前半の可能な合計

なし     → 0
10       → 10
25       → 25
30       → 30
10+25    → 35
10+30    → 40
25+30    → 55
10+25+30 → 65

後半の可能な合計

なし     → 0
15       → 15
20       → 20
35       → 35
15+20    → 35
15+35    → 50
20+35    → 55
15+20+35 → 70

Step 3: 最適な組み合わせを探す

前半の各合計に対して、「後半から足しても100を超えない最大値」を探す。

// 前半の合計 + 後半から選べる最大 = 合計

前半 0  → 後半で100以下の最大 = 70 → 合計 70
前半 10 → 後半で90以下の最大  = 70 → 合計 80
前半 25 → 後半で75以下の最大  = 70 → 合計 95
前半 30 → 後半で70以下の最大  = 70 → 合計 100 ★最適！
前半 35 → 後半で65以下の最大  = 55 → 合計 90
前半 40 → 後半で60以下の最大  = 55 → 合計 95
前半 55 → 後半で45以下の最大  = 35 → 合計 90
前半 65 → 後半で35以下の最大  = 35 → 合計 100 ★同率！

答え

合計100（前半30 + 後半70、または前半65 + 後半35）

二分探索による高速化

Step 3で「条件を満たす最大値」を探すとき、後半の合計リストをソートしておけば二分探索で一瞬で見つかる。

// 後半の合計リスト（ソート済み）
[0, 15, 20, 35, 35, 50, 55, 70]

// 「70以下の最大は？」
→ 二分探索で即座に「70」と判明（8要素でも最大3回の比較）

今回の計算結果

最適な計上合計

¥7,240,250

目標金額 ¥7,240,268

差額 ¥18

処理内容

35件の配当金データを前半17件・後半18件に分割。前半で約13万通り、後半で約26万通りの部分和を計算し、二分探索で最適な組み合わせを特定。処理時間は約1秒（全探索なら9時間以上）。

除外する項目（5件）

行	金額	判定
3	¥4,000	除外
17	¥8,000	除外
18	¥44,000	除外
19	¥20,000	除外
24	¥15,120	除外

計上する項目（30件）

行	金額	判定
2	¥4,000	計上
4	¥1,140	計上
5	¥1,140	計上
6	¥18,000	計上
7	¥57,681	計上
8	¥75,429	計上
9	¥29,500	計上
10	¥28,000	計上
11	¥80,000	計上
12	¥75,000	計上
13	¥60,000	計上
14	¥85,000	計上
15	¥80,000	計上
16	¥54,000	計上
20	¥2,497,000	計上
21	¥2,610,500	計上
22	¥132,000	計上
23	¥132,000	計上
25	¥16,800	計上
26	¥100,000	計上
27	¥105,000	計上
28	¥30,000	計上
29	¥30,000	計上
30	¥5,460	計上
31	¥1,000	計上
32	¥1,100	計上
33	¥32,000	計上
34	¥361,500	計上
35	¥179,000	計上
36	¥358,000	計上

30件

計上する項目

5件

除外する項目

99.9997%

目標達成率

付録：自分で計算する方法

計算の難しさについて

この問題は「部分和問題」と呼ばれ、データ件数が増えると計算量が爆発的に増加します。Excelの標準機能では解けません。

件数と対応方法の目安

〜20件：Excel + ソルバーで対応可能
20〜40件：AIツール（Gemini/ChatGPT等）を推奨
40件以上：専用プログラムが必要

Gemini / ChatGPT に依頼する場合

以下のプロンプトをコピーして、データ部分を差し替えて使用してください。

Gemini / ChatGPT 用プロンプト

以下の金額リストから、合計が【目標金額】を超えないように、かつ最大限近づく組み合わせを見つけてください。

■ 目標金額
7,240,268円（この金額を超えてはいけない）

■ 金額リスト（1行1件）
4000
4000
1140
1140
18000
57681
75429
29500
28000
80000
75000
60000
85000
80000
54000
8000
44000
20000
2497000
2610500
132000
132000
15120
16800
100000
105000
30000
30000
5460
1000
1100
32000
361500
179000
358000

■ 出力形式
1. 計上する項目の一覧（行番号と金額）
2. 除外する項目の一覧（行番号と金額）
3. 計上合計金額
4. 目標金額との差額

■ 注意事項
- 各金額は「計上する」か「しない」かの二択です
- 数学的に最適な解を求めてください
- 近似解ではなく、厳密な最適解をお願いします

Excelソルバーを使う場合（20件以下向け）

データ準備

A列に金額、B列に判定用（0または1）、C列に A×B の計算式を入れる

ソルバー起動

データ → ソルバー（なければアドインから有効化）

設定

目的：C列合計を最大化／制約：C列合計 ≦ 目標金額、B列は0か1のみ

まとめ：アルゴリズムの美しさ

Meet-in-the-Middle法の本質

「半分に分ける」というシンプルな発想で、計算不可能な問題を1秒で解ける問題に変える。これがアルゴリズムの力。

分割統治

大きな問題を小さく分けて解く

指数の性質

2^n を 2×2^(n/2) に変換

二分探索

ソートと探索で効率化