パスワードを忘れた? アカウント作成
13914129 story
数学

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

ストーリー by hylom
この組み合わせは流行るのか 部門より

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

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

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

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

  • by Oh-MissSpell (37716) on 2019年05月22日 7時48分 (#3618836) 日記

    こんなに食べても1000円以内におさまるなんて、
    実質カロリーゼロなのでは?

    ここに返信
  • 手計算 (スコア:3, 興味深い)

    by Anonymous Coward on 2019年05月22日 6時56分 (#3618819)

    dbファイル [github.com]があるから、そっから

    1. カロリー未記載のものを除外
    2. 同じ値段のものは一番カロリーが高いもの以外除外
    3. それ以下の値段でより多くカロリーが摂れるもの(価格ソートでカロリーが下がってる奴)を除外
    4. 一つ下の値段の商品に最安1~2番目メニュー(トッピング半熟卵69円90kCal/セットプチフォッカ79円107kCal)を加えたものにカロリー(と値段)が負けてる商品を除外

    すると12品残った。途中でミスってそうだけど。
    まぁ後は手計算できなくもないと判断したが、自分的には力尽きた。
    Excelでもいいから手計算しない方が楽なぎりぎりレベルだと感じるな。

    ちなみにExcelの人とはメニューが若干違うので注意(ラージライスとかがなかった)。

    この手の作業、BDとかに焼く時に毎回やってるな。
    以前全探索で詰め込む簡単なプログラムを作ったけど10だか20だか程度なら普通に解けるのよね。
    でも実際は多少余っても構わないし、というかBDはパケットライトのUDFの都合とかで合計値より結構余計に容量を消費するし、関連した奴らをまとめたいしで手作業でやってる。というかほぼ適当にやってるだけだな。

    プログラマらしからぬ。

    ここに返信
    • Re:手計算 (スコア:2, 参考になる)

      by Anonymous Coward on 2019年05月22日 7時48分 (#3618835)

      2の手順で最適解を見落とすバグを仕込んでますね
      500yen 500 kcal
      500yen 400 kcal
      400yen 200 kcal
      100yen 100 kcal
      では
      900 kcalが最適だけど
      2の作業をすると800kcalになる

      金額1000円までで取りうる値が整数値限定なら、動的計画法一択でしょ

      • by Anonymous Coward

        重複有効なら2では下がらない。
        3(と多分4)は普通にバグだと思うけど……

      • by Anonymous Coward

        ホントだ。
        途中までは重複ありのつもりで考えていて、「あ重複禁止なんだ、まぁいいや」って続行したんでおかしな事になってる。

        • by Anonymous Coward on 2019年05月22日 12時13分 (#3618990)

          その「まあいいや」がバグの元だってのは業務で嫌と言うほどあじわってるでしょ?

        • by Anonymous Coward

          まあ価格、カロリー、利用可能回数の組で考えればいいわけだが。
          3の手順は、価格×利用可能回数分で1000円を超える場合のみ、それより割の悪いものを消せばいい。

      • by Anonymous Coward

        可能性で言うなら3の手順でも最適解を排除する可能性があるよーな。

        500yen 400kcal
        400yen 500kcal
        300yen 200kcal
        200yen 100kcal
        100yen 50kcal

        最適は500yen、400yen、100yenの950kcalだけど、
        3の手順で500yenのメニューを除外しちゃうと850kcalになる。

        • by Anonymous Coward

          4も。コスパ最悪の1円 0.0001 kcal みたいな商品が除外されてしまう。それで最後に余った端数を使い切れば、その分合計値は上がる。

          • by Anonymous Coward

            1以外は何もできませんという結論に。

            # 1,000円を超える品の除去ぐらいしかできない?

            • by Anonymous Coward

              4の件を書いたけど、読み間違いかも。
              でもまあ、NP困難なので、よほど明白な枝刈り以外は全探索するしかない。探索途中で、その先を探索しても、今まで見つかっている内で一番良い解に出来得なかったらそこで止めるとかその手の。

    • by Anonymous Coward

      ラージライスはメニューにあるよ

  • by Anonymous Coward on 2019年05月22日 7時29分 (#3618825)

    税込みなんでしょうね。
    ざっとメニューを見て
    チキン南蛮定食にゴボウの唐揚げで+半熟卵で2172Kcal
    ごはん大盛り無料ですから、何カロリーになるか?

    ここに返信
  • この発端となったサイゼリヤ1000円ガチャ [qiita.com]、楽しいですよね。
    https://saizeriya-1000yen.herokuapp.com/ [herokuapp.com]

    このアプリではドリンクのカロリーが0kcalで計算されるのが難点ですが、
    プチフォッカセットの上にフォッカチオが出たり、
    ハンバーグだけで終わってしまったりで笑ってしまいます。
    思わずサイゼリヤに行きたくなってしまう

    --
    一人以外は全員敗者
    それでもあきらめるより熱くなれ
    ここに返信
  • by Anonymous Coward on 2019年05月22日 9時29分 (#3618884)

    ドリンクバーのコーヒーに砂糖たっぷり×たくさんおかわり

    ってのはなしだよな、たぶん。

    ここに返信
    • by Anonymous Coward

      大丈夫ドリンクバーのジュースをおかわりし続けるだけさ

  • by Anonymous Coward on 2019年05月22日 10時10分 (#3618908)

    えー自分でお湯入れる必要はありますが
    ただただカロリー欲しけりゃこれ食う

    ここに返信
    • スーパーの閉店時間が近くなると、
      揚げ玉が25cm×20cm×4cmくらいの容器に詰まったものが
      30円とか50円でよく売られているけど、あれの値段あたりカロリーはかなりのものかと想像。
      菓子代わりに何度か買って食ってみたことあるけど、腹持ちは相当する。
      ただしそういう使い方は体に悪いかも・・・?

    • by Anonymous Coward

      キューピーマヨネーズ450g(250円ぐらい?)なら1本で3000キロカロリー取れるぞ?

    • by Anonymous Coward

      一番の問題はサイゼリヤのメニューにはないことだな

  • 日本の世間的(特にスラド住人)にはカロリーは減らすことを考えるべきでは……

    ここに返信
    • by Anonymous Coward

      むしろ運動不足ばかりだろうから
      動いて代謝を良くすべきかと

  • by Anonymous Coward on 2019年05月22日 11時33分 (#3618966)

    > 一般には多項式時間で解けないNP困難な問題とされている。

    メニューの品揃えが少なければ、有限の組み合わせで解けそうな気がします。
    サイゼリアのメニュー数(数十種類くらい?)だと、手作業でできるギリギリってくらいでしょうか。

    上限金額を抑えれば組み合わせ可能数が減りますね。

    ここに返信
    • by Anonymous Coward

      組み合わせの多い/少ないは問題の種類を規定しません.

      「巡回セールスマン問題」はたしか全米50州で厳密解が知られているかと.

  • by Anonymous Coward on 2019年05月22日 12時19分 (#3618992)

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

    ドリンクバー(280円)を注文して甘いもの飲み続ければ、店を追い出されるまで際限無くカロリーを摂取できるぞ。
    1注文だけだから、重複なしで条件も満たしている。

    ここに返信
    • by Anonymous Coward

      オリーブオイルを飲み続ければもっと安く出来る

      • by Anonymous Coward

        してみると、まったく何も注文しないで居座るわけにはいかないだろうから、
        サイゼリヤメニューの中で最低価格であるグラスワイン(100円)を1品注文して、
        あとは妖怪のようにオリーブオイルをぴちゃぴちゃ舐めているのが正解というわけか。

        すごい献立だw

      • by Anonymous Coward

        グラスワイン120mlで約90kCalなので、目標を記事中の1940kCalに設定すると残り約1850kCal。
        オリーブオイルは100gあたり約920kCalらしいので、約200g飲まないと越えられないのか。

        ちなみにオリーブオイルの比重は0.9前後なので約222ml。サイゼリヤのオリーブオイルの瓶は500mlなので、約4/9飲む計算。
        安いことは安いがキツいなあ。

  • by Anonymous Coward on 2019年05月22日 14時10分 (#3619049)

    カロリー最低のメニューは!

    と思ったが、
    お茶飲んでろで終わる話だった。

    ここに返信
typodupeerror

アレゲはアレゲを呼ぶ -- ある傍観者

読み込み中...