概要
この記事や後述の先行研究に触発されて、「サイゼリヤで1000円あれば最大何kcal摂れるのか」を最も単純に全探索で解いてみました。
先行研究
先人たちがいろいろな方法で解決を試みています。
実装
あらかじめ実装したものがこちらになります。
メニューデータは
にあるmenu.csvをダウンロードしてきました（make時に自動でダウンロードされます）
実装の注意点としては、探索の途中で合計金額があらかじめ指定した金額(1000円)を超えるような組み合わせは調べないようにしています。*1
実際に計算してみます。
$ ./solve 1000 Loading menu... Solving... Solved! ラージライス: 219 yen, 454 kcal アーリオ・オーリオ(Wサイズ): 574 yen, 1120 kcal ポテトのグリル: 199 yen, 366 kcal Price: 992 yen Calorie: 1940 kcal
先行研究の結果と一致しているので正しく計算できているようです。
私の手元のPCでは0.4秒弱で計算が終わりました。全探索しても大したことなかったですね。
つまり数々のアルゴリズムはすべて無駄だったわけです。
…というわけではなく、この方法だと上限金額を大きくするとあっという間に計算時間が爆発します。
試しに1500円で計算させたところ、30秒弱かかりました。1000円から1700円程度までの実行時間を元に予測すると、おおよそ指数的に計算時間が増えて、2000円だと30分程度、3000円だと100日程度かかってしまう計算になります。
手法によっては10000円でも現実的な時間で解くことができているので、サイゼリヤで豪遊したい場合はアルゴリズムを学ぶことが必須なことがわかります。
感想
もっと計算時間がかかるかと思っていたので拍子抜けしています。本当はGPGPUで殴って楽しい高速化ライフ！という記事にしたかったのですが…
*1:この工夫を入れないと2115通り調べることになり計算が終わりません、合法な組み合わせすべてを試すので全探索と主張することは許して…
