プチコン 非公式コミュニティ
トピック
こういち
◆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/23 21:55
◆ou0jbJnEJ0Kb
落ち着け…俺。こういう場合は一度効率が悪くとも動くプログラムを書いてから高速化すればいい。
とりあえずkを
k=1 300円以上のメニューを注文している
k=2 グリルを注文している
とする。
問題はk=0のときどうするか…
とりあえずkを
k=1 300円以上のメニューを注文している
k=2 グリルを注文している
とする。
問題はk=0のときどうするか…
あきと
2019/10/24 1:36
◆Q/mp.qcMuPYu
詰め合わせる内容でコストが変動してしまうとナップザック問題が成立しないので、セットメニューやトッピング追加した時の複数のメニューを組み合わせると値段が下がる場合は新しいメニューとして追加すればいいのではないのでしょうか。とりあえず全ての値段リストを作成してしまうという考え方です。
MENUMAX=xx ' 単品で注文した場合のメニューの総数
N=xx ' 組み合わせでどれだけできるか分からないのでたくさん
MENUCOST[MENUMAX,2] 'メニューのカロリーと単品の値段
MENULIST[N,1+3] '0に値引き結果の値段を入れる。3は組み合わせの上限,
まずはジョナサ…レストランJのメニューのカロリーと値段をDATAに記述してMENUCOSTに読み込みます。
次にMENULISTに単品で頼んだ時の値段としてMENUCOSTの値段とメニュー番号を格納します。
[300、0,-1,-1] ’[値段,メニュー番号、なし、なし]を表現
[350、1,-1,-1]
[280、2,-1,-1]
・・
[700,29,-1,-1] '例えば30種類の単品メニューだった場合
次にメニューを複数組み合わせたときに値引きが発生する条件を判定する関数を作ってMENUCOST同士の組み合わせを総当たりします。
値引き判定関数を通して単品同士よりも値段が安くなる組み合わせだった場合はMENULISTの下に新しく追加します。その際にペアを記入していきます。
0番と15番を組み合わせたら値引きが発生した場合
[300, 28,-1,-1]
[700, 29,-1,-1] 'ここまで単品メニューの値段リスト
[480, 0,15,-1] '←ここから値引きリストを追加(0と15番はセット値段で安くなった
…
値段が変動する組み合わせを新しくMENULISTにどんどん追加していきます。
カロリーはMENULISTの番号からMENUCOSTを参照して総カロリー数を算出する関数を作ります。
MENULISTを参照すれば値引き後の値段が分かる状態を作ってからナップザック問題を解けばいいのかなと思って書いてみました。
トッピングをいくつも追加できるとMENULISTが増えすぎてしまうのでまあ一種類だけとかに限定してみれば総当たりの爆発は起きないのでは。
MENUMAX=xx ' 単品で注文した場合のメニューの総数
N=xx ' 組み合わせでどれだけできるか分からないのでたくさん
MENUCOST[MENUMAX,2] 'メニューのカロリーと単品の値段
MENULIST[N,1+3] '0に値引き結果の値段を入れる。3は組み合わせの上限,
まずはジョナサ…レストランJのメニューのカロリーと値段をDATAに記述してMENUCOSTに読み込みます。
次にMENULISTに単品で頼んだ時の値段としてMENUCOSTの値段とメニュー番号を格納します。
[300、0,-1,-1] ’[値段,メニュー番号、なし、なし]を表現
[350、1,-1,-1]
[280、2,-1,-1]
・・
[700,29,-1,-1] '例えば30種類の単品メニューだった場合
次にメニューを複数組み合わせたときに値引きが発生する条件を判定する関数を作ってMENUCOST同士の組み合わせを総当たりします。
値引き判定関数を通して単品同士よりも値段が安くなる組み合わせだった場合はMENULISTの下に新しく追加します。その際にペアを記入していきます。
0番と15番を組み合わせたら値引きが発生した場合
[300, 28,-1,-1]
[700, 29,-1,-1] 'ここまで単品メニューの値段リスト
[480, 0,15,-1] '←ここから値引きリストを追加(0と15番はセット値段で安くなった
…
値段が変動する組み合わせを新しくMENULISTにどんどん追加していきます。
カロリーはMENULISTの番号からMENUCOSTを参照して総カロリー数を算出する関数を作ります。
MENULISTを参照すれば値引き後の値段が分かる状態を作ってからナップザック問題を解けばいいのかなと思って書いてみました。
トッピングをいくつも追加できるとMENULISTが増えすぎてしまうのでまあ一種類だけとかに限定してみれば総当たりの爆発は起きないのでは。
こういち
2019/10/24 5:41
◆ou0jbJnEJ0Kb
あきとさん
実はそれちょっと考えてたんですが、セットメニューとトッピング両方を付けた場合とか考えるとメモリと計算量が凄いことになりそうだと思ってやめました。
あと、青い鳥で見かけた2000キロカロリー越えの組み合わせとかはセットメニューを複数頼んでた(ライスおかわりとか)ので、やっぱりセットメニューやトッピングは複数付けられないとたどり着けない境地があるな…と。
とは言え今のが難しそうなら試してみます。
実はそれちょっと考えてたんですが、セットメニューとトッピング両方を付けた場合とか考えるとメモリと計算量が凄いことになりそうだと思ってやめました。
あと、青い鳥で見かけた2000キロカロリー越えの組み合わせとかはセットメニューを複数頼んでた(ライスおかわりとか)ので、やっぱりセットメニューやトッピングは複数付けられないとたどり着けない境地があるな…と。
とは言え今のが難しそうなら試してみます。
やきはた
2019/10/24 8:20
◆pmVfuH0n4Kcn
300円以下を試すプログラムと３００円以上を試すプログラムの２種類を作成したらいいと思います。
そしたら分岐はコード開始時点だけで済みます。
１つのデータを
メニュー番号 金額 カロリー メニュー名
とします。
dp[金額]=-1とします。
-1は候補なしとします。
dpを計算して
dp2[金額]=その金額ピッタリで到達できるカロリーの最大値
dp[金額]＝その金額ぴったりで最後に買うメニューの番号とします。
具体的なメニュー付きで計算結果を表示する手法。
A
dp終了後 金額の最大値から1円までiとします。
まずi円１つを見る時
その１
dp[i]=-1でなければ
空配列にメニュー番号を積み、そのメニューのカロリーを足しあげます
次に
i=i-そのメニューの金額
として
その１に戻り
０円に到達するまで計算します。
後は全てのi円でAを繰り返し一番カロリーの高い結果を残していけば答えは出ます。
C++と違って秒間１０億回が期待できないプチコン特有の悩みですね。
メニューの最大合計金額は幾らでメニュー数が幾らか分からないと答えにくい問題です。
そしたら分岐はコード開始時点だけで済みます。
１つのデータを
メニュー番号 金額 カロリー メニュー名
とします。
dp[金額]=-1とします。
-1は候補なしとします。
dpを計算して
dp2[金額]=その金額ピッタリで到達できるカロリーの最大値
dp[金額]＝その金額ぴったりで最後に買うメニューの番号とします。
具体的なメニュー付きで計算結果を表示する手法。
A
dp終了後 金額の最大値から1円までiとします。
まずi円１つを見る時
その１
dp[i]=-1でなければ
空配列にメニュー番号を積み、そのメニューのカロリーを足しあげます
次に
i=i-そのメニューの金額
として
その１に戻り
０円に到達するまで計算します。
後は全てのi円でAを繰り返し一番カロリーの高い結果を残していけば答えは出ます。
C++と違って秒間１０億回が期待できないプチコン特有の悩みですね。
メニューの最大合計金額は幾らでメニュー数が幾らか分からないと答えにくい問題です。
こういち
2019/10/24 8:51
◆ou0jbJnEJ0Kb
やきはたさんありがとうございます。
後でじっくり考えてみます。配列再利用派ですか。
さて、簡単な場合から考えようと、全探索を考えたけど、高速化のために、長らく再帰を使ってないせいで再帰が書けない体質になっていた件。
後でじっくり考えてみます。配列再利用派ですか。
さて、簡単な場合から考えようと、全探索を考えたけど、高速化のために、長らく再帰を使ってないせいで再帰が書けない体質になっていた件。
こういち
2019/10/24 10:24
◆ou0jbJnEJ0Kb
やきはたさん
もう少し詳しく教えて頂けないでしょうか。
dp2[金額]=その金額ピッタリで到達できるカロリーの最大値→分かる
dp[金額]＝その金額ぴったりで最後に買うメニューの番号とします。→分かる
具体的なメニュー付きで計算結果を表示する手法。→分かる
後は全てのi円でAを繰り返し→全てのメニューでAを繰り返しでは？
300円以下を試すプログラムと３００円以上を試すプログラムの２種類を作成したらいいと思います。→分からない
もう少し詳しく教えて頂けないでしょうか。
dp2[金額]=その金額ピッタリで到達できるカロリーの最大値→分かる
dp[金額]＝その金額ぴったりで最後に買うメニューの番号とします。→分かる
具体的なメニュー付きで計算結果を表示する手法。→分かる
後は全てのi円でAを繰り返し→全てのメニューでAを繰り返しでは？
300円以下を試すプログラムと３００円以上を試すプログラムの２種類を作成したらいいと思います。→分からない
こういち
2019/10/24 10:31
◆ou0jbJnEJ0Kb
さて、k作戦について、kについて考えてみました。
k=0 全てのメニューで最適な組み合わせ
k=1 300円以上のメニューを含む中で最適な組み合わせ
k=2 グリルを含む中で最適な組み合わせ
つまり、全てのi,jについて
dp[i,j,0]>=dp[i,j,1]>=dp[i,j,2]
が保証されると仮定する。
k=0 全てのメニューで最適な組み合わせ
k=1 300円以上のメニューを含む中で最適な組み合わせ
k=2 グリルを含む中で最適な組み合わせ
つまり、全てのi,jについて
dp[i,j,0]>=dp[i,j,1]>=dp[i,j,2]
が保証されると仮定する。
こういち
2019/10/24 12:00
◆ou0jbJnEJ0Kb
そうすると、商品iを注文しない場合、
kがk以上の値を再利用できる。
注文する場合、
メニューiがトッピングなら、k=2の値のみを再利用出来る。
セットメニューなら、k>=1の値
それ以外なら、全てのkの値を再利用出来る。
kがk以上の値を再利用できる。
注文する場合、
メニューiがトッピングなら、k=2の値のみを再利用出来る。
セットメニューなら、k>=1の値
それ以外なら、全てのkの値を再利用出来る。
こういち
2019/10/24 12:14
◆ou0jbJnEJ0Kb
あっ。もしかしたら出来たかもしれないです。
'value[i] メニューiの値段
'cal[i] カロリー
'type[i] 種類 1:300円以上 2:グリル 3:セットメニュー 4:トッピング
'N メニューの総数
'W 予算の最大値
for i=1to N '全てのメニューに対して
t=type[i]
v=value[i]
c=cal[i]
for j=0to W '全ての予算に対して
k=3
repeat '全てのkに対して
k=k-1
if v<j then '注文可能なら
dp[i,j,k]=max(dp[i-1,j,k],dp[i-1,j-v,(t<k||t>2)*max(k,t-2)]+c) '注文した場合としてない場合のカロリーが高いほう
else
dp[i,j,k]=dp[i-1,j,k]
endif
until k==0
next j
next i
'value[i] メニューiの値段
'cal[i] カロリー
'type[i] 種類 1:300円以上 2:グリル 3:セットメニュー 4:トッピング
'N メニューの総数
'W 予算の最大値
for i=1to N '全てのメニューに対して
t=type[i]
v=value[i]
c=cal[i]
for j=0to W '全ての予算に対して
k=3
repeat '全てのkに対して
k=k-1
if v<j then '注文可能なら
dp[i,j,k]=max(dp[i-1,j,k],dp[i-1,j-v,(t<k||t>2)*max(k,t-2)]+c) '注文した場合としてない場合のカロリーが高いほう
else
dp[i,j,k]=dp[i-1,j,k]
endif
until k==0
next j
next i
こういち
2019/10/24 12:42
◆ou0jbJnEJ0Kb
あっ。ダメだこれ。dp[i,j,1]とかに300円未満のメニューしか入っていない可能性がある。
まぁdp[0,j,1]とdp[0,j,2]を1<<31とかで初期化しとけばいっか。(雑)
さて、これで予算以内のカロリーの最大値が求まったので、そのカロリーを達成できるメニューの組み合わせを求めなければ。dp配列を逆に辿っていってもいいけど、今回は面倒そうなので、やきはたさんのやり方を採用します。
…とその前に重複ありの方も作ろう。
連続コメント失礼しました。
まぁdp[0,j,1]とdp[0,j,2]を1<<31とかで初期化しとけばいっか。(雑)
さて、これで予算以内のカロリーの最大値が求まったので、そのカロリーを達成できるメニューの組み合わせを求めなければ。dp配列を逆に辿っていってもいいけど、今回は面倒そうなので、やきはたさんのやり方を採用します。
…とその前に重複ありの方も作ろう。
連続コメント失礼しました。
やきはた
2019/10/24 18:07
◆pmVfuH0n4Kcn
出勤前の６分で書いたので言葉足らずでした。
３００円注文するまでグリルやセットメニューを注文できないなら
まずグリルとセット以外のメニューでDPして、その後で３００円以上からセットやグリルをDPします。
DPをDPとDP2の二つの配列を利用して解きます。
DP2は普通に金額を配列の添え字に最大カロリーを価値とした動的計画法です。
DP２で更新で来たらDPで同じ添え字を更新します。
それが出来たらメニュー候補をDPから取り出します。
DP2を0で初期化します。
DP3を答えを取り出すための配列とします。
最大金額から１円まで逆向きループでiを使います。
DP[i]<>-1ならば
if DP2[i-DP[i]の値段]<(DP[i]（配列の中身はメニュー番号だから）それのカロリー+DP2[i]) then
DP2[i-DP[i]の値段]=DP[i]のカロリー+DP2[i]
DP3[i-DP[i]]=DP[i]
ループが終われば
後はDP3[0]からメニューが取り出せるのは自明です。
C++で参考コードを書いてideon.comにでも置いておきましょうか。
３００円注文するまでグリルやセットメニューを注文できないなら
まずグリルとセット以外のメニューでDPして、その後で３００円以上からセットやグリルをDPします。
DPをDPとDP2の二つの配列を利用して解きます。
DP2は普通に金額を配列の添え字に最大カロリーを価値とした動的計画法です。
DP２で更新で来たらDPで同じ添え字を更新します。
それが出来たらメニュー候補をDPから取り出します。
DP2を0で初期化します。
DP3を答えを取り出すための配列とします。
最大金額から１円まで逆向きループでiを使います。
DP[i]<>-1ならば
if DP2[i-DP[i]の値段]<(DP[i]（配列の中身はメニュー番号だから）それのカロリー+DP2[i]) then
DP2[i-DP[i]の値段]=DP[i]のカロリー+DP2[i]
DP3[i-DP[i]]=DP[i]
ループが終われば
後はDP3[0]からメニューが取り出せるのは自明です。
C++で参考コードを書いてideon.comにでも置いておきましょうか。
やきはた
2019/10/24 19:17
◆pmVfuH0n4Kcn
https://ideone.com/S6yVEr
C++での参考コードです(修正前の版には一か所記述ミスがあったまあこれで大丈夫)。
サンプルインプットは
１行目が予算
２行目がメニューの数
それ以降はメニューデータ
１列目がメニューのタイプ（セットかグリルなら１でなければ0です）
２列目はメニューの番号（0から始まる）
３列目は金額
４列目はカロリーです。
サンプルインプットの金額設定が難しいせいかプログラムミスか、３００円を超えるまで同じメニュー、越えたらやはり同じメニューばかり注文するのが答えになっています。
C++での参考コードです(修正前の版には一か所記述ミスがあったまあこれで大丈夫)。
サンプルインプットは
１行目が予算
２行目がメニューの数
それ以降はメニューデータ
１列目がメニューのタイプ（セットかグリルなら１でなければ0です）
２列目はメニューの番号（0から始まる）
３列目は金額
４列目はカロリーです。
サンプルインプットの金額設定が難しいせいかプログラムミスか、３００円を超えるまで同じメニュー、越えたらやはり同じメニューばかり注文するのが答えになっています。
こういち
2019/10/29 8:39
◆ou0jbJnEJ0Kb
やきはたさん
文化祭で忙しかったり、実はC++読めなかったり(蟻本読みまくってるやつが何を言う)、continueに苦手意識があったりで遅れましたが、読んでみました。
配るdpですか。
内容は理解しましたが、何故これで動くのかは理解できていないので、もう少し考えてきます。
文化祭で忙しかったり、実はC++読めなかったり(蟻本読みまくってるやつが何を言う)、continueに苦手意識があったりで遅れましたが、読んでみました。
配るdpですか。
内容は理解しましたが、何故これで動くのかは理解できていないので、もう少し考えてきます。
こういち
2019/10/29 12:32
◆ou0jbJnEJ0Kb
やきはたさん
理解しました。
2回DPする感じですね。
今回の場合、単品300円以上のメニューにセットを付けることが出来るって感じなので、問題には合わないなと思いました。ボクの説明不足でした。すみません。
ただ、配るDpのやり方とか参考になりました。ありがとうございます。
理解しました。
2回DPする感じですね。
今回の場合、単品300円以上のメニューにセットを付けることが出来るって感じなので、問題には合わないなと思いました。ボクの説明不足でした。すみません。
ただ、配るDpのやり方とか参考になりました。ありがとうございます。
やきはた
2019/10/29 18:29
◆pmVfuH0n4Kcn
他人のコードを理解できる能力ってプログラムの世界で一番大事な学習能力ですね。
他人のコードを読める能力は、ハッカーになる人が一番最初に獲得し最も長期にわたり成長させる重要な能力。
私にはない能力なので尊敬します。
蟻本仲間ですね。
競プロはどの言語で？
私は一時Haskellを嗜んでおりました。
おっととプチコン以外の会話はあまりしてはいけないのでした。
他人のコードを読める能力は、ハッカーになる人が一番最初に獲得し最も長期にわたり成長させる重要な能力。
私にはない能力なので尊敬します。
蟻本仲間ですね。
競プロはどの言語で？
私は一時Haskellを嗜んでおりました。
おっととプチコン以外の会話はあまりしてはいけないのでした。
- 1
- 2
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります