プチコン 非公式コミュニティ
トピック
こういち
◆ou0jbJnEJ0Kb
2019/10/23 21:25
2019/10/23 21:25
質問
変則ナップサック問題
ボクはよく、とある有名なファミリーレストラン(以下Jとする)に行くのですが、ふと予算内(例えば1000円)で最大どれだけカロリーを摂取できるのか気になり、最大カロリーを解くプログラムを書こうと思い立ちました。
Jのメニューを調べてみたら、300円以上のメニューを注文すると、セットメニューを付けることが出来るらしく、さらに、グリル(グリルは全て300円以上)を注文すると、トッピングを付けることが出来るらしいです。
ちょっと複雑なシステムなので、プログラムを書くのに苦労しています。
テンプレ通り、dp[i,j]という配列に
「i番目までのメニューで、j円以内で摂取できる最大カロリー」の情報を格納することにすると、グリルや300円以上のメニューを注文したかどうかが分からないので、
新たにkの次元を追加して、
dp[i,j,k]という配列に最大カロリー格納することすることにしましたが、その先どうすればいいのかが分かりません。
どなたか助けていただけないでしょうか。
ちなみに、同じメニューを注文しない場合(いわゆる0-1ナップサック問題)と、同じメニューを複数注文できる場合(個数制限なしナップサック問題)の両方を求めたいです。
Jのメニューを調べてみたら、300円以上のメニューを注文すると、セットメニューを付けることが出来るらしく、さらに、グリル(グリルは全て300円以上)を注文すると、トッピングを付けることが出来るらしいです。
ちょっと複雑なシステムなので、プログラムを書くのに苦労しています。
テンプレ通り、dp[i,j]という配列に
「i番目までのメニューで、j円以内で摂取できる最大カロリー」の情報を格納することにすると、グリルや300円以上のメニューを注文したかどうかが分からないので、
新たにkの次元を追加して、
dp[i,j,k]という配列に最大カロリー格納することすることにしましたが、その先どうすればいいのかが分かりません。
どなたか助けていただけないでしょうか。
ちなみに、同じメニューを注文しない場合(いわゆる0-1ナップサック問題)と、同じメニューを複数注文できる場合(個数制限なしナップサック問題)の両方を求めたいです。
コメント
こういち
2019/10/29 21:52 ネタバレ
◆ou0jbJnEJ0Kb
やきはた
2019/10/30 7:54 ネタバレ
◆pmVfuH0n4Kcn
こういち
2019/10/30 8:10
◆ou0jbJnEJ0Kb
やきはたさん
はい。難解言語のあれです。本当に使うのは稀ですが。
ベターCはちょっと考えたのですが、強めの型安全性が気に入らないな…と。
さて、セットメニューですが、単品価格300円(正確には299円+税)以上のメニューを注文すると、セットメニューを付けられる感じです。
例えば、単品599円+税のビーフカレーに199円+税プラスで和食セットを付けられる…みたいな。(組み合わせのセンス)
そう考えるとボクのプログラムは300円以上のメニューにいくつもセットメニューを付けられるので、正確とは言えませんね。
それとは別にハンバーグやステーキなどのグリルメニュー(グリルは全て299円+税以上の値段)にはエビフライや唐揚げなどのトッピングを付けることが出来ます。(こちらは多分グリルひとつにいくらでも付けられる)
はい。難解言語のあれです。本当に使うのは稀ですが。
ベターCはちょっと考えたのですが、強めの型安全性が気に入らないな…と。
さて、セットメニューですが、単品価格300円(正確には299円+税)以上のメニューを注文すると、セットメニューを付けられる感じです。
例えば、単品599円+税のビーフカレーに199円+税プラスで和食セットを付けられる…みたいな。(組み合わせのセンス)
そう考えるとボクのプログラムは300円以上のメニューにいくつもセットメニューを付けられるので、正確とは言えませんね。
それとは別にハンバーグやステーキなどのグリルメニュー(グリルは全て299円+税以上の値段)にはエビフライや唐揚げなどのトッピングを付けることが出来ます。(こちらは多分グリルひとつにいくらでも付けられる)
やきはた
2019/10/30 18:15
◆pmVfuH0n4Kcn
ブレインファックは何回か書いたことありますが文字数増えがち。
私の1/3位の文字数で正答してるの見ると頭の出来が違うのかなと思ったりしますが中身を読解する能力は無いです。
セット グリル それ以外を基本と定義します。
基本1品頼むとセットを一品追加できる基本注文数＞＝セット注文数。
基本1品頼むとグリルを何品でも追加できる。
この感じですか？
私の1/3位の文字数で正答してるの見ると頭の出来が違うのかなと思ったりしますが中身を読解する能力は無いです。
セット グリル それ以外を基本と定義します。
基本1品頼むとセットを一品追加できる基本注文数＞＝セット注文数。
基本1品頼むとグリルを何品でも追加できる。
この感じですか？
こういち
2019/10/30 19:51
◆ou0jbJnEJ0Kb
BFは四則演算はもちろん実数や4バイト整数が無いのが普通にツラい。
単品価格が300円以上の品ひとつにつきセットを1つ注文出来る。
グリルを1品頼むとトッピングをいくらでも付けられる。
単品価格が300円以上の品ひとつにつきセットを1つ注文出来る。
グリルを1品頼むとトッピングをいくらでも付けられる。
やきはた
2019/10/30 20:18
◆pmVfuH0n4Kcn
仕様がどんどん複雑になってきますね。
どんな処理をしたいか整理できるまでお返事を出せそうもあり前ん。
どんな処理をしたいか整理できるまでお返事を出せそうもあり前ん。
こういち
2019/11/1 8:28
◆ou0jbJnEJ0Kb
ライスおかわりはともかく、やはり1つのメニュー(大盛りポテトフライ)にセットが複数つく(和食セットとセットライス)結果になりました。
まぁここまでは想定内。
追記
1<<32は1<<31の間違いでした。
あと、ルール追加で｢ライスおかわり(108円)はセットメニューの個数にカウントされない。(単品300円以上のメニューを注文しないと注文できないのは変わらず)｣
こういち
2019/11/1 8:29
◆ou0jbJnEJ0Kb
こういち
2019/11/1 10:33
◆ou0jbJnEJ0Kb
さて、セットメニューの数が300円以上のメニュー数を越えないようにプログラムを改造したい。
まず思い付くのが、
kの示す状態を
k=1 300円以上のメニュー数がセットメニューの数より多い
みたいにすること。
そうすると、新たに300円以上-セットメニューの値を保持する配列が必要になる。
そして、重要なことで、
dp[i,j,1]>=dp[i,j,2]
が成立しなくなる。厄介。
あとライスおかわりが数に含まないの厄介。
まず思い付くのが、
kの示す状態を
k=1 300円以上のメニュー数がセットメニューの数より多い
みたいにすること。
そうすると、新たに300円以上-セットメニューの値を保持する配列が必要になる。
そして、重要なことで、
dp[i,j,1]>=dp[i,j,2]
が成立しなくなる。厄介。
あとライスおかわりが数に含まないの厄介。
Na
2019/11/1 22:36
◆QoELVrBXBQCI
「300円以上-セットメニューの値」や「グリルを注文したかどうか」っていう情報は保持しても意味ないと思います。
セットをつけられる個数を保持しておいて後でセットをつけるのと、300円の商品を買った時点でセットをつけるのは実質同じですよね?
見当違いなこと言ってたらすみません。
セットをつけられる個数を保持しておいて後でセットをつけるのと、300円の商品を買った時点でセットをつけるのは実質同じですよね?
見当違いなこと言ってたらすみません。
こういち
2019/11/2 9:35
◆ou0jbJnEJ0Kb
Naさん
>>300円の商品を買った時点でセットをつけるのは実質同じですよね?<<
問題はセットを付けるか付けないかを選ぶことが出来る点なんですよね。
仮にそれが出来たとしても、セットと300円以上のメニューはたくさんあるので、セットの種類*300円以上のメニューの種類の組み合わせの数はとんでもないことになるかと。そもそもこれ以上遅くしたくはない。
>>300円の商品を買った時点でセットをつけるのは実質同じですよね?<<
問題はセットを付けるか付けないかを選ぶことが出来る点なんですよね。
仮にそれが出来たとしても、セットと300円以上のメニューはたくさんあるので、セットの種類*300円以上のメニューの種類の組み合わせの数はとんでもないことになるかと。そもそもこれ以上遅くしたくはない。
Na
2019/11/2 9:49
◆QoELVrBXBQCI
>こういちさん
それでもセットを付けるか付けないかを選ぶのを後回しにする必要はなくないですか?
たとえば0番目のメニューが300円で100kcal、セットが100円で10kcalだとして、
dp[i,j]に「i番目までのメニュー(とそれにつけられるセットすべて)で、j円以内で摂取できる最大カロリー」を入れることにすると、
dp[0,300]=100、dp[0,400]=110となり、これでどちらの場合も考慮できているのでこれでいいのでは?
それでもセットを付けるか付けないかを選ぶのを後回しにする必要はなくないですか?
たとえば0番目のメニューが300円で100kcal、セットが100円で10kcalだとして、
dp[i,j]に「i番目までのメニュー(とそれにつけられるセットすべて)で、j円以内で摂取できる最大カロリー」を入れることにすると、
dp[0,300]=100、dp[0,400]=110となり、これでどちらの場合も考慮できているのでこれでいいのでは?
こういち
2019/11/2 10:21
◆ou0jbJnEJ0Kb
それはセットに対する計算をi回行っていて非効率では？
for 全てのメニューに対して
for 全てのセットに対して
for 全ての値段に対して
みたいになって遅くなりそう。
for 全てのメニューに対して
for 全てのセットに対して
for 全ての値段に対して
みたいになって遅くなりそう。
Na
2019/11/2 10:27
◆QoELVrBXBQCI
たしかに
こういち
2019/11/2 10:29
◆ou0jbJnEJ0Kb
それから、解が求まったあと、メニューの組み合わせを復元できるかどうか…
あと、同じメニューを複数頼みそう。
あと、同じメニューを複数頼みそう。
SatoshiMcCloud
2019/11/2 12:14
◆Z1qfV11i63Jr
自分もチャレンジしたいんですが、メニューの一覧をもらえませんか？
こういち
2019/11/2 15:39
◆ou0jbJnEJ0Kb
手打ちになりますが｢ジョイフル メニュー｣で検索していただければ。
まだ全部入力したわけではないですが、テストしたやつもあげときます。
【4BDX7E8V】
全部入力したわけではないとは言っても、入力していないのは明らかに不要な低カロリーメニューと、注文できないお子さまセット、アルコールと時間帯に左右されるランチぐらいですが。
まだ全部入力したわけではないですが、テストしたやつもあげときます。
【4BDX7E8V】
全部入力したわけではないとは言っても、入力していないのは明らかに不要な低カロリーメニューと、注文できないお子さまセット、アルコールと時間帯に左右されるランチぐらいですが。
SatoshiMcCloud
2019/11/2 21:52
◆Z1qfV11i63Jr
ありがとうございます。いまは出先なので、帰ったらダウンロードします。
こういち
2020/1/29 12:48
◆ou0jbJnEJ0Kb
ツイッターでサイゼリヤガチャがトレンド入りしてたので久しぶりにここにやってきた。
サイゼリヤ問題を効率的に解くアルゴリズムでも見つかったのかなとか思ったけど、特に何もなかった模様。
相変わらず変則ジョイフル問題は解けそうにない。
サイゼリヤ問題を効率的に解くアルゴリズムでも見つかったのかなとか思ったけど、特に何もなかった模様。
相変わらず変則ジョイフル問題は解けそうにない。
こういち
2020/7/2 11:45
◆.Id/aHiU36hu
…！
bitDPを使えば…
bitDPを使えば…
- 1
- 2
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります