「サイゼリヤで、合計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]

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

Re:手計算

[Anonymous Coward]

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

Re:

[Anonymous Coward]

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