最近，巷では「サイゼリヤで1000円あれば最大何kcal摂れるのか」を計算するのが流行っているようです。
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。 - Qiita
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。 - Qiita
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。 - Qiita
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。 - Qiita
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をExcel のソルバーでで解いてみた。 - Qiita
- 【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法 - わえなび ワード＆エクセル問題集
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をなでしこでDPで解いてみた。 - Qiita
しかし，「サイゼリヤで1000円あれば最大何kcal摂れるのか」をLaTeX文書化して組版することを考えたとき，
- 何らかのプログラミング言語を用いて「サイゼリヤで1000円あれば最大何kcal摂れるのか」を計算する。
- その結果をLaTeXソースとして打ち込んで文書化・組版してPDFを得る。
というのではいかにも二度手間です。TeX言語はプログラミング言語でもあるのだから，計算と組版を一気にやってしまいましょう！😏
解法
上記の記事では，量子アニーリング計算やSMTソルバーなどを使って解かれていますが，この問題は典型的な0-1ナップサック問題の構造をしているので，動的計画法(DP)で解くのが標準的です。
TeX言語で解いた結果
（中略）
というわけで，先人たちの試みと同じ結果が得られました！
（イメージ図：tanakh
さんの記事より）
（実写写真：わえなび ワード＆エクセル問題集さんの記事より）
LaTeX文書ソース
サイゼリヤのメニュー一覧は saizeriya.db （SQLite DB形式）から取得しました。また，計算量削減のため，ゼロカロリーのメニュー項目（ドリンク類）は除去してあります。
生成PDFはこちらです。
コンパイルにあたっての注意点
TeX Live のデフォルト設定では，上記LaTeX文書はメモリ不足でコンパイルできませんでした。texmf.cnf において
main_memory = 6000000 pool_size = 16250000
にしてフォーマットファイル再作成をしたところ，コンパイルを通せました。
