「サイゼリヤで、合計1000円以内で摂取できるカロリーの最大値は1940kcal」記事へのコメント

手計算

[Anonymous Coward]

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

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

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

ちなみにExcel

Re:

[Anonymous Coward]

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

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

Re:手計算

[Anonymous Coward]

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

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

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

Re:

[Anonymous Coward]

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

Re:

[Anonymous Coward]

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

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

Re:

[Anonymous Coward]

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

Re:

[Anonymous Coward]

重複禁止における4の反例。
931yen,1089kcal
861yen,1000kcal
79yen,107kcal
69yen,90kcal
この場合、
861+69=930yen,1000+90=1090kcal
となり一位は二位にカロリーと値段両面で負ける。
で二位以下での最高値は
861+79=940yen,1000+107=1107kcal
一方一位を残すと
931+69=1000yen,1089+90=1179kcal

まぁ単純に
500yen,1000kcal
430yen,1001kcal
でも反例になるが。