Elevenのハンバーガー屋さんを《攻略》する~組合せ最適化問題~

はじめに

エターナルリターンのWebイベント「Elevenのハンバーガー屋さん」を見て誰もがこう思った。
これ、組合せ最適化問題だ。なら解いてしまおうじゃん。
ヒョヌにもわかるように解説！

イベントのリンク

Eleven's Diner! | Eternal Return

《攻略》するWebアプリ

Elevenのハンバーガー屋さん攻略

組み合わせ最適化問題とは

文字通り、最も良い組み合わせを求める問題のこと。
例を挙げると、

• 新聞を配って回る時の最短ルートは何か（巡回セールスマン問題）

• 決められた予算内でおやつを買うとき、何をいくつ買うのが一番良いか（ナップザック問題）

これらの問題は、全パターン調べれば当然答えはわかる。
ただし、それは厳しい。

例えば47都道府県すべて1回は通る日本1周ルートを考える。これはパターンが多すぎて、全て調べるのはスーパーコンピューターで何万年もかかってしまう。もちろんこれは無駄なパターン（北海道->沖縄->青森->…みたいな明らか無駄なやつ）も無視せずちゃんと調べたときの話

工夫して調べる（あるいは妥協する）のがこの問題のメイン。
これを踏まえてイベント内容を見てみよう。

Elevenのハンバーガー屋さん問題

さあ、配信の始まりだよ～！

今日の配信テーマは文化祭で出す「Elevenのハンバーガー屋さん」だよ！

食材箱から材料を手に入れて、

ハンバーガー作りを手伝ってくれたらプレゼントをあげるね！

Elevenのコメントより

要はプレゼント獲得のために、コインをたくさん集めたいわけだ。そのためにはバーガーを作る必要がある。
作れるバーガーは4種類ある。どれをいくつ作るのがスマートチョイス・・・？

材料交換しないで作る場合

材料交換はいったん置いといて、手元の材料でバーガーを作れるだけ作ることを最初に考える。何をいくつ作れば一番コインを稼げるか。
以降、材料セットを下図のように [a,b,c,d,e,f] という形式で表現する。

この場合 [13,11,1,2,2,2] と表す

レシピは次の図

材料をたくさん使うバーガーはコインも多くもらえる

バーガー作りの方針はいろいろ考えられる。おや？何名かは早速バーガー作りを手伝っているようだ

エキオンの考え方

考えるという行為と無縁の実験体エキオンは、手当たり次第、気分で交換する模様。
「効率的なバーガー作りだぁ？そんなのはバカが考えることだ！」だそう。
しかし [1,1,1,1,1,1] の材料で50コインのElevenバーガーを作れるのに、14コインのハンバーガーを作って材料がなくなってしまいました。これはいけません。

ジェニーの考え方

高価なものが好きな女優ジェニーは、高いものから順に作れる最大まで作っていく模様。一見良さそうだが果たして。
[2,2,2,1,1,0] の材料でダブルパティバーガーを1個だけ作って終了。
しかしチーズバーガー1個、ハンバーガー1個を作ると 14+22=36コインでわずかにこちらのほうが良い。
他にも、[2,2,2,2,1,0] ならダブルパティバーガー1個（35コイン）よりもチーズバーガー2個（22x2=44コイン）のほうが良くて、結構差が出る。
高いものから作っても最適解になるとは限らないことがわかった。

JPの考え方

天才ハッカーのJP（ハンドルネーム）は、自らプログラムを書いても解けるけれども、遊びでChatGPTに解かせようとしている。

以下の問題を解くプログラムをpythonで書いて：
6つの材料[a,b,c,d,e,f]を使ってできるハンバーガーの4レシピがある。レシピを作ると以下に示すコインを獲得するが、使った材料は消費される：
1. [1,1,1,0,0,0] = 14コイン
2. [1,1,1,1,0,0] = 22コイン
3. [1,1,2,1,1,0] = 35コイン
4. [1,1,1,1,1,1] = 50コイン
入力は各材料の個数がカンマ区切りで与えられる。材料の個数は0 以上の整数である。与えられた材料を消費し、獲得コインが最大となる各レシピの作成数を求めよ。

実際にChatGPTに送った文

```python
ingredients = list(map(int, input().split(',')))
recipe1 = [1,1,1,0,0,0]
recipe2 = [1,1,1,1,0,0]
recipe3 = [1,1,2,1,1,0]
recipe4 = [1,1,1,1,1,1]

max_coins = 0
max_counts = [0, 0, 0, 0]

for i in range(min(ingredients[0]//recipe1[0], ingredients[1]//recipe1[1], ingredients[2]//recipe1[2])):
    for j in range(min((ingredients[0]-i*recipe1[0])//recipe2[0], (ingredients[1]-i*recipe1[1])//recipe2[1], (ingredients[2]-i*recipe1[2])//recipe2[2], ingredients[3]//recipe2[3])):
        for k in range(min((ingredients[0]-i*recipe1[0]-j*recipe2[0])//recipe3[0], (ingredients[1]-i*recipe1[1]-j*recipe2[1])//recipe3[1], (ingredients[2]-i*recipe1[2]-j*recipe2[2])//recipe3[2], (ingredients[3]-j*recipe2[3])//recipe3[3], (ingredients[4]-i*recipe1[4])//recipe3[4])):
            l = min(ingredients[0]-i*recipe1[0]-j*recipe2[0]-k*recipe3[0], ingredients[1]-i*recipe1[1]-j*recipe2[1]-k*recipe3[1], ingredients[2]-i*recipe1[2]-j*recipe2[2]-k*recipe3[2], ingredients[3]-j*recipe2[3]-k*recipe3[3], ingredients[4]-i*recipe1[4]-k*recipe3[4], ingredients[5]-recipe4[5])
            coins = i*14 + j*22 + k*35 + l*50
            if coins > max_coins:
                max_coins = coins
                max_counts = [i, j, k, l]

print(max_counts)

上記プログラムは実際にChatGPTが回答したもので、全パターン調べるアプローチになっている（バグがあって完全ではない）。
ちなみに筆者が作ったアプリも上記ソースコードをたたき台として作成した。面白い時代になったものだ。
調べ方のイメージとしては、以下のような樹形図が視覚的にわかりやすいだろうか。

各バーガーを何個作るかの樹形図、材料はできるだけ使い切る

開始時点で材料は確定しており、各バーガーをいくつ作るか全パターン調べる。材料は余らせないほうが明らかに良いので、最後のElevenバーガーはその時点で余っている材料で作れるだけ作る。

さて全パターン調べるのは大変なことも多いが、パターンが少ないならば文句なしに最適解が求まるわけだ。
今回のイベントは、期間（25日）と1日に貰える材料（12個）から、どんなに多くても材料の合計は25x12=300個になる。300個の材料では、3つの材料でできるハンバーガーは最大で100個しか作れない。
上記プログラムの計算でいくと、レシピに使う材料の個数から考えるに、最悪の場合でも 100x75x50=375000回ほど計算すればよく、これはコンピュータにとっては一瞬。しかも実際にはもっとパターンは少ない。
つまり、今回の条件では全パターン調べる方法で全く問題ない。もっと効率よく最良のパターンを見つける方法があるかもしれないが。

ここまでで、材料を交換しないという条件下では、全パターン調べる方法が有効だとわかった。
ちなみに全パターン調べる方法を「全探索」と言う。

厄介な存在、材料交換

親切なElevenは、好きな材料と好きな材料とで 3:1 交換してくれるという（ベーコンは交換に出すことももらうことも不可能）。
これはありがたい！パンだけ集まりすぎたとき、パンを3つ消費してレタスやトマトをゲットできるなんて。
なんて、厄介な条件だろう

交換はいつでも何度でもできるため、最初に全ての交換を済ませてしまい、バーガーを作っている途中に交換しない方向で考えて問題ない。
と、いうことは、Elevenのハンバーガー屋さん問題を分解すると次のようになる：

1. 与えられた材料セットを好きな回数（0でもよい）適当に材料交換して、新たな材料セットを作り出す

2. 1.で作り出した材料セット全てについて、全探索で最適なバーガーの組み合わせを求める。こうして最もコインが獲得できる答えをベストアンサーにする

これで解ける！が、1.の問題が簡単ではない。
材料交換をして新たな材料セットを作り出す、これは材料3->1に変換するため、合計材料数はだんだん減っていく。しかしこのパターンの中には明らかに無駄な交換パターンも含まれる。
例えば、パン9個をチーズ3個に換え、そのあとチーズ3個をパン1個に換える。これは明らかに無駄な材料交換。

このような明らかに無駄な交換を除き、交換を続けてできたすべての材料セットについて全探索をすれば現実的な時間内に答えが求まることになった。無駄な交換としてプログラムに組み込んだ部分は実際にソースコードを見てもらえれば良いと思う。

ここで使ったように無駄を省いて効率よく探索する方法は枝狩りとか分枝限定法とか呼ばれているが、卒論…ウっ頭が…

筆跡はここで途切れている