サイゼリヤで合計1000円以内で摂取できるカロリー、最大値は1940kcal

　ファミリーレストラン「サイゼリア」で、1,000円以内で食べられるメニューの組み合わせで摂取できる最大カロリーを計算で求める手法が一部界隈で盛り上がっている。

　発端は、『「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。』という記事。これに触発され、さまざまな手法でこの問題を解く人達が登場している（【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法）。

　「1,000円以内で食べられるメニューの組み合わせで摂取できる最大カロリーを求める」という問題はナップサック問題などと呼ばれる組み合わせ最適化問題であり、一般には多項式時間で解けないNP困難な問題とされている。

　なお、これら記事によると、重複無しで合計1000円以下となるように注文したとき、最大のカロリー摂取量は1940kcalになるそうだ。

　スラドのコメントを読む | サイエンスセクション | プログラミング | 数学

　関連ストーリー：
東芝、組み合わせ最適化問題の近似解を得る新アルゴリズムを開発。並列処理で大幅な高速化が可能 2019年04月23日
3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に？ 2011年01月24日
粘菌が組み合せ最適化問題を解く 2008年04月14日