「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。 - Qiita

はじめに 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。 N番煎じですが、これらの記事を見てマルコフ連鎖モンテカルロで解いてみました。コードは以下に置いてあります。 https://github.com/kaityo256/saizeriya_mc 方針 全メニューについて、「注文する/しない」を0/1の状態ベクトルとして、そのベクトルについて最適化をかけます。カロリーをエネルギーとして、カロリーを最大化するようにします。試行は「メニューの追加/削除」の二種類です。状態の更新はメトロポリス法を使います。すると、メニューの追加試行は