TeX Alchemist Online

TeX を使って化学のお仕事をしています。

「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する ~TeX言語で動的計画法(DP)~

最近,巷では「サイゼリヤで1000円あれば最大何kcal摂れるのか」を計算するのが流行っているようです。

しかし,「サイゼリヤで1000円あれば最大何kcal摂れるのか」をLaTeX文書化して組版することを考えたとき,

  1. 何らかのプログラミング言語を用いて「サイゼリヤで1000円あれば最大何kcal摂れるのか」を計算する。
  2. その結果をLaTeXソースとして打ち込んで文書化・組版してPDFを得る。

というのではいかにも二度手間です。TeX言語はプログラミング言語でもあるのだから,計算と組版を一気にやってしまいましょう!😏

解法

上記の記事では,量子アニーリング計算やSMTソルバーなどを使って解かれていますが,この問題は典型的な0-1ナップサック問題の構造をしているので,動的計画法(DP)で解くのが標準的です。

ja.wikipedia.org

TeX言語で解いた結果

f:id:doraTeX:20190520123906p:plain

(中略)

f:id:doraTeX:20190520124004p:plain

というわけで,先人たちの試みと同じ結果が得られました!

f:id:doraTeX:20190520124220p:plain

(イメージ図:tanakh さんの記事より)

https://cdn-ak.f.st-hatena.com/images/fotolife/w/waenavi/20190519/20190519203006.jpg

LaTeX文書ソース

サイゼリヤのメニュー一覧は saizeriya.db (SQLite DB形式)から取得しました。また,計算量削減のため,ゼロカロリーのメニュー項目(ドリンク類)は除去してあります。

gist.github.com

生成PDFはこちらです。

コンパイルにあたっての注意点

TeX Live のデフォルト設定では,上記LaTeX文書はメモリ不足でコンパイルできませんでした。texmf.cnf において

main_memory = 6000000
pool_size = 16250000

にしてフォーマットファイル再作成をしたところ,コンパイルを通せました。