福袋っす(1)

提出された課題をチェックしてたらこんな時間っす。

今回のネタに関するスクリプトは書けてないっす。

明日になるっすね。

どうもぺんぎんっす( ◎v◎ )

とっても面白そうなネタが投下されたっす。

福袋なんっすけど、もちろん自分の商品じゃないっすよ。

福袋を箱詰めする際の、その組み合わせ方についてっす。

今日は問題提示だけになりそうっす。

中に入れるモノにはそれぞれ「価値」が割り振られてるっす。

いくつかモノを組み合わせて価値の合計が「設定値」の

範囲内に収めたいわけっす。

ついでにその組み合わせ方を列挙もしたいっす。

あ、同じモノを2つ以上入れるのはナシっす。

組み合わせ方のパターンは膨大になって面倒なので

スクリプトで解かせようというものっす。

具体的に問題を見て行くっす。

list CONTENTS_AND_VALUES = // モノの名前, 重み

[

　　　"product01", 10,

"product02", 10,

"product03", 20,

"product04", 20,

"product05", 30,

"product06", 30,

"product07", 40,

"product08", 40,

"product09", 50,

"product10", 50

];

こんな感じのlistが与えられるっす。

要素数も変わると思ってた方が良いっすね。

これと「設定値」、例えば[合計90から110]が共に与えられた時

考えられる組み合わせを全部出せという問題っす。

組み合わせの1つとしては

product03　20

product06　30

product10　50

で、価値を合計すると100になるので設定値を満たすっす。

パターン数は

モノを1個選ぶ……₁₀C₁

モノを2個選ぶ……₁₀C₂

モノを3個選ぶ……₁₀C₃

　・

　・

　・

モノを10個選ぶ……₁₀C₁₀

これの合計数になるっす。(面倒なので計算はしてないっす)

モノが10種類なので大したことないんっすけど、

20種類、30種類となるとかなりの数になるっす。

product03-product06-product10の組み合わせを発見したら、

product03-product10-product06

product06-product03-product10

product06-product10-product03

product10-product06-product03

product10-product03-product06

っていう組み合わせも見つけちゃう可能性があるっす。

これは価値大→価値小の順に探索を進めて行けば

防げるっす。同価値の場合はlistのインデックス順っす。

product03-product06-product10のケースだと

product10-product06-product03の1通りになるっす。

自分は深さ優先探索でやろうと思ってるんっすけど

皆さんならどうやるっすかね？