※この記事は、2025年6月に開催されたイベントでの発表内容をレポートしたものです。
- おやつは300円まで！という問題
- お菓子の種類について
- 組み合わせを1つ1つ調べると？3種類で考えてみる
- おやつは300円まで！は難しい問題（組み合わせ爆発が起きる）
- 効率的な2つの解法
- 2つの解法の結果を比較する
- 結論：ケースバイケースで使い分ける
- まとめ
登壇者はこの方
小澤 陽介 氏
パーソルキャリア株式会社
リードデータアナリスト
前職では機械系メーカーR&Dにて数理最適化のアプリケーション開発及び工程可視化に従事。パーソルキャリア入社後、アナリストとして、主に生成系AIに関連するアプリケーション開発や検証に従事。現在はグループ企業向けのML推薦システム構築に携わっている。
小澤：私はパーソルキャリアでリードアナリストを務めている小澤と申します。転職サービス「doda」などの事業に携わる中で、日々さまざまな業務に取り組んでいます。
今回は、誰にとっても身近な「おやつは300円まで！」という問題を、プログラミングを使って組み合わせ最適化問題として解いてみました。
さらに、2つのプログラミング言語と2つのアルゴリズムを使い、計算スピードも比較してみました。
この発表を皆様に楽しんでいただけたら幸いです。
おやつは300円まで！という問題
遠足のおやつ選びを想像してみてください。合計300円までしかお菓子が買えないというルール、経験がある方も多いのではないでしょうか。
遠足に行く子供のおやつ選びを想定します。
この問題を解くにあたり、「満足度」という曖昧な表現を、より客観的な「合計カロリー」に置き換えて考えます。
つまり、「300円の予算内で、最も合計カロリーが高くなるお菓子の組み合わせは何か？」という問題です。
お菓子の種類について
まずは、お菓子のデータを用意しました。インターネットで調べた50種類のお菓子のデータをもとに、最適解を導き出します。
組み合わせを1つ1つ調べると？3種類で考えてみる
これらのデータをもとに、「300円以内」という制約の中で「カロリーが最大」になる組み合わせを選んでいきますが、実はこの問題は非常に難しい問題です。
組み合わせを一つ一つ調べる方法を考えてみましょう。例えば、お菓子の種類が3種類だけの場合を想定します。ここでは「0」は買わない、「1」は買うという意味で表現します。
もし「うまい棒」と「キャベツ太郎」の2種類だけであれば、組み合わせは4通りで済みます。
しかし、ここに「ポテトフライ」という選択肢が加わった瞬間、これまでの4通りのそれぞれに対して「ポテトフライを買うか、買わないか」の選択肢が加わるため、組み合わせの数は倍になります。
3種類のお菓子であれば、組み合わせは全部で8通りとなり、これを一つ一つ調査すれば最適解を見つけることができます。
この場合の合計金額は72円なので、300円の予算内で、合計186kcalとなる「全部買う」のが最適解だとわかります。
おやつは300円まで！は難しい問題（組み合わせ爆発が起きる）
今回は50種類のお菓子を扱っています。お菓子の種類が1つ増えるごとに、組み合わせは倍々で増えていきます。
50種類の場合、その組み合わせの総数は2の50乗となり、これは1125京という天文学的な数になります。
これら全ての組み合わせを調べようとすると、仮に全ての駄菓子を買った場合、お値段は3,737円となり300円の予算を大幅に超えてしまうため、この選択肢はあり得ないことは直感的に分かります。では全ての組み合わせを一つ一つ調べていくとどうなるでしょうか。
非常にざっくりとした計算ですが、仮に一般的なノートPCでこの計算を実行した場合、およそ7万年以上かかってしまうという結果になりました。つまり、この問題は「組み合わせ最適化問題」と呼ばれる非常に解くのが難しい問題なのです。
もし、この組み合わせ最適化問題に対する効率的な解法を知らなければ、すべての組み合わせをしらみつぶしに調べるしかありません。
上記のようにもし子供に「お母さん、300円以内でカロリーが最大になるようにお菓子を買って！」と言われても、「7万年くらいかかるから諦めてね」と答えるしかなくなってしまいます。
しかしそういうわけにはいかないため、今回は効率的な解法を試してみることにします。
効率的な2つの解法
ここからは、私が試してみた解法について説明します。大きく分けて「近似解法」と「厳密解法」の2種類の方法があります。
1. 近似解法：貪欲法
1つ目は、「貪欲法」という近似解法です。これは、各要素に評価値をつけて、その評価値が高い順に選んでいくシンプルなアルゴリズムです。
メリットとしては、実装が簡単であること、そして多くの問題が多項式時間、つまり比較的短い時間で終わることが挙げられます。
一方で、デメリットとしては、問題によっては厳密な最適解が得られない場合があることです。
それでは、この貪欲法を適用してみましょう。
今回は評価値として、簡単に「コスパ」、つまり1円あたりでどれだけカロリーが取れるかを求めます。これは単純にカロリーを値段で割れば計算できます。
例えば、ヤングドーナツは195kcalで47円なので、1円あたり約4.15kcalとなり、非常にコスパが良いことがわかります。このように計算したコスパの順に駄菓子をソートし、コスパが高い順に選んでいきます。その際、合計金額が300円を超えないのであればその駄菓子をナップサックに加え、超える場合はスキップします。全ての駄菓子をチェックし終えたら、アルゴリズムは終了です。
この方法は、コスパの計算とソート、そして一通りのチェックだけで済むため、非常に簡単な解法です。
上図が貪欲法による答えです。この解の品質については、後ほど詳しくお話しします。
2. 厳密解法：整数計画法
2つ目は、「整数計画法」という厳密解法です。
この手法では、「お菓子を買うか、買わないか」という選択を、数学的に変数（0または1）で表現します。そして、「合計金額が300円以内」という制約条件と、「合計カロリーを最大化する」という目的関数を設定し、専用のツール（ソルバー）で解を求めます。
- メリット： 必ず最適な答え（厳密解）が得られることが保証されている。
- デメリット： 実装には数学的な知識が必要で、計算に時間がかかる場合がある。
今回は、無料の数理最適化ソルバー「OR-Tools」を利用して、この問題を解きました。
厳密解放の答え
駄菓子の購入額は300円が上限です。そして、満足感を最大化するように駄菓子を買います。先ほども述べましたが、「満足感」という言葉を「カロリーが高い」という表現に置き換えます。
次に、定数と変数を定義します。駄菓子の総数をN個とし、各駄菓子にIDを割り振ります。そして、駄菓子iのカロリーをci、値段をpiと設定します。変数としては、駄菓子iを購入する場合は1、購入しない場合は0をとる変数xiを定義します。
これらを用いて、制約式と目的関数を定義します。制約式は、購入する駄菓子の合計金額が300円以内になることを表します。これは、各駄菓子の値段（pi）とその駄菓子を買うかどうか（xi）の積の総和が300以下であるという式で表現できます。次に目的関数ですが、これは購入した駄菓子の総カロリーを最大化することを目的とします。各駄菓子のカロリー（ci）とxiの積の総和を最大化（maximize）するように設定します。
今回は、私が個人的に好きなC#と、よく利用するPythonの2種類の言語でコーディングを行いました。その結果得られた厳密解法の答えは以下の通りです。
ただ、この結果だけを見ても分かりにくいかと思いますので、まずは解の品質について、2つの手法を比較してみましょう。
2つの解法の結果を比較する
解の品質：どちらの解法が優れている？
貪欲法と整数計画法の解を比較してみると、結果は以下のようになりました。
- 貪欲法：合計957.7kcal
- 整数計画法： 合計964kcal
整数計画法の方がわずかに高いカロリーで、より良い組み合わせを見つけ出しました。この結果から、やはり厳密解法の方が解の品質は優れていることがわかります。
しかし、貪欲法も非常に近い結果を出しており、実用上は十分に使えるレベルだと言えます。
処理速度：どちらの解法が早い？
次に、処理速度を比較しました。
- 貪欲法：約35マイクロ秒（1マイクロ秒 = 0.000001秒）
- 整数計画法：約700マイクロ秒
今回の問題サイズの場合、貪欲法は整数計画法よりも約20倍高速でした。ただし、どちらも1ミリ秒未満で計算が終わるため、体感的には差はありません。
これは、貪欲法がシンプルな計算で済むのに対し、整数計画法は複雑な計算処理を行うためです。
結論：ケースバイケースで使い分ける
2つの解法を比較した結果をまとめると、以下のようになります。
計算速度は近似解法（貪欲法）の方が速く、厳密解法は遅いです。最適性については、近似解法は必ずしも最適解を得られるとは限らないのに対し、厳密解法は最適であることを保証します。
使いどころとしては、近似解法は「そこそこの品質の解が素早く欲しい時」に適しており、厳密解法は「問題のサイズが十分に小さい時」に有効です。
実用的には、多くの場合、近似解で十分なことが多いでしょう。また、今回の問題サイズのように比較的小さなものであれば、厳密解法でもさほど時間はかかりません。結論として、問題の特性に応じて、ケースバイケースで言語や手法を使い分けるのが望ましいと言えます。
まとめ
今回は、駄菓子選びという身近なテーマを組み合わせ最適化問題として捉え、解法の比較についてお話ししました。他にも様々な解法がありますが、今回は代表的で分かりやすいものを選んでご紹介しました。この発表を通して、皆さんが最適化という分野に少しでも面白さを感じていただけたら幸いです。
そして最後になりますが、もしお子様に同じような問題を頼まれた際には、最適化の結果にこだわらず、お子様の好きな順番でお菓子を買ってあげてくださいね。
▼▼ ぜひ他登壇者の発表レポートもご覧ください！
おやつは300円まで！の最適化を模索してみた
小澤 陽介さんの発表内容については、以下の記事リンクからご覧ください。
市町村のオープンデータを使って「公園・トイレの口コミマップ」を作ってみた
うーたんさんの発表内容については、以下の記事リンクからご覧ください。
スマートハウスの蓄電性能の効率化を実現してみた〜電気自動車編〜
ななみんさんの発表内容については、以下の記事リンクからご覧ください。
総額200円の入力インターフェースで年齢問わず楽しめる体験型展示
豊田陽介さん の発表内容については、以下の記事リンクからご覧ください。
