アカウント名:
パスワード:
dbファイル [github.com]があるから、そっから
すると12品残った。途中でミスってそうだけど。まぁ後は手計算できなくもないと判断したが、自分的には力尽きた。Excelでもいいから手計算しない方が楽なぎりぎりレベルだと感じるな。
ちなみにExcelの人とはメニューが若干違うので注意(ラージライスとかがなかった)。
この手の作業、BDとかに焼く時に毎回やってるな。以前全探索で詰め込む簡単なプログラムを作ったけど10だか20だか程度なら普通に解けるのよね。でも実際は多少余っても構わないし、というかBDはパケットライトのUDFの都合とかで合計値より結構余計に容量を消費するし、関連した奴らをまとめたいしで手作業でやってる。というかほぼ適当にやってるだけだな。
プログラマらしからぬ。
2の手順で最適解を見落とすバグを仕込んでますね500yen 500 kcal500yen 400 kcal400yen 200 kcal100yen 100 kcalでは900 kcalが最適だけど2の作業をすると800kcalになる
金額1000円までで取りうる値が整数値限定なら、動的計画法一択でしょ
重複有効なら2では下がらない。3（と多分4）は普通にバグだと思うけど……
ホントだ。途中までは重複ありのつもりで考えていて、「あ重複禁止なんだ、まぁいいや」って続行したんでおかしな事になってる。
その「まあいいや」がバグの元だってのは業務で嫌と言うほどあじわってるでしょ？
まあ価格、カロリー、利用可能回数の組で考えればいいわけだが。3の手順は、価格×利用可能回数分で1000円を超える場合のみ、それより割の悪いものを消せばいい。
可能性で言うなら3の手順でも最適解を排除する可能性があるよーな。
500yen 400kcal400yen 500kcal300yen 200kcal200yen 100kcal100yen 50kcal
最適は500yen、400yen、100yenの950kcalだけど、3の手順で500yenのメニューを除外しちゃうと850kcalになる。
4も。コスパ最悪の1円 0.0001 kcal みたいな商品が除外されてしまう。それで最後に余った端数を使い切れば、その分合計値は上がる。
1以外は何もできませんという結論に。
# 1,000円を超える品の除去ぐらいしかできない？
4の件を書いたけど、読み間違いかも。でもまあ、NP困難なので、よほど明白な枝刈り以外は全探索するしかない。探索途中で、その先を探索しても、今まで見つかっている内で一番良い解に出来得なかったらそこで止めるとかその手の。
重複禁止における4の反例。931yen,1089kcal861yen,1000kcal79yen,107kcal69yen,90kcalこの場合、861+69=930yen,1000+90=1090kcalとなり一位は二位にカロリーと値段両面で負ける。で二位以下での最高値は861+79=940yen,1000+107=1107kcal一方一位を残すと931+69=1000yen,1089+90=1179kcal
まぁ単純に500yen,1000kcal430yen,1001kcalでも反例になるが。
ラージライスはメニューにあるよ
「レビューは大事」という事が分かる良いスレッド。
「手作業のあたたかみ」の危険性もよく分かる
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
吾輩はリファレンスである。名前はまだ無い -- perlの中の人
手計算 (スコア:3, 興味深い)
dbファイル [github.com]があるから、そっから
すると12品残った。途中でミスってそうだけど。
まぁ後は手計算できなくもないと判断したが、自分的には力尽きた。
Excelでもいいから手計算しない方が楽なぎりぎりレベルだと感じるな。
ちなみにExcelの人とはメニューが若干違うので注意(ラージライスとかがなかった)。
この手の作業、BDとかに焼く時に毎回やってるな。
以前全探索で詰め込む簡単なプログラムを作ったけど10だか20だか程度なら普通に解けるのよね。
でも実際は多少余っても構わないし、というかBDはパケットライトのUDFの都合とかで合計値より結構余計に容量を消費するし、関連した奴らをまとめたいしで手作業でやってる。というかほぼ適当にやってるだけだな。
プログラマらしからぬ。
Re:手計算 (スコア:2, 参考になる)
2の手順で最適解を見落とすバグを仕込んでますね
500yen 500 kcal
500yen 400 kcal
400yen 200 kcal
100yen 100 kcal
では
900 kcalが最適だけど
2の作業をすると800kcalになる
金額1000円までで取りうる値が整数値限定なら、動的計画法一択でしょ
Re: (スコア:0)
重複有効なら2では下がらない。
3（と多分4）は普通にバグだと思うけど……
Re: (スコア:0)
ホントだ。
途中までは重複ありのつもりで考えていて、「あ重複禁止なんだ、まぁいいや」って続行したんでおかしな事になってる。
Re:手計算 (スコア:1)
その「まあいいや」がバグの元だってのは業務で嫌と言うほどあじわってるでしょ？
Re: (スコア:0)
まあ価格、カロリー、利用可能回数の組で考えればいいわけだが。
3の手順は、価格×利用可能回数分で1000円を超える場合のみ、それより割の悪いものを消せばいい。
Re: (スコア:0)
可能性で言うなら3の手順でも最適解を排除する可能性があるよーな。
500yen 400kcal
400yen 500kcal
300yen 200kcal
200yen 100kcal
100yen 50kcal
最適は500yen、400yen、100yenの950kcalだけど、
3の手順で500yenのメニューを除外しちゃうと850kcalになる。
Re: (スコア:0)
4も。コスパ最悪の1円 0.0001 kcal みたいな商品が除外されてしまう。それで最後に余った端数を使い切れば、その分合計値は上がる。
Re: (スコア:0)
1以外は何もできませんという結論に。
# 1,000円を超える品の除去ぐらいしかできない？
Re: (スコア:0)
4の件を書いたけど、読み間違いかも。
でもまあ、NP困難なので、よほど明白な枝刈り以外は全探索するしかない。探索途中で、その先を探索しても、今まで見つかっている内で一番良い解に出来得なかったらそこで止めるとかその手の。
Re: (スコア:0)
重複禁止における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
でも反例になるが。
Re: (スコア:0)
ラージライスはメニューにあるよ
Re: (スコア:0)
「レビューは大事」という事が分かる良いスレッド。
Re: (スコア:0)
「手作業のあたたかみ」の危険性もよく分かる