部活7

部活です。

お題は変わらず。

予告どおり99枚のパネルから最高得点の部分和がS-pとなるような19枚のパネル群を抽出することについて。ナップサック問題の特殊な例と考えることができます。

①品物(パネル)は99個

②各品物には価値(最高得点)と重さ(すべて1)が与えられる

③ナップサックに入れられる重さは19丁度であり、多くても少なくてもダメ

当然、すべての品物の重さが1であるため、価値の高い順に入れれば最高得点の和の最大値が求まります。(=S)

今回求めるべきはS-pとなる場合の部分集合ですので、Sの場合の結果を利用してみます。

①最高得点の同値類をまとめる

②部分和がSとなる①の組み合わせを決定する

③②の要素から1引いた値となる同値類を選択し、S-1の組み合わせとする

簡単に説明します。

①については、最高点が同値のものをグループにまとめることです。

　15点:ゲーム機(ニンテンドー3DSは15点。なんで？)

　14点:ジュース、メガネ、電車、UFO

　　　･･･

　  6点:ふで

②について、今回は、S=234点となります。このときの選び方は

　{15,14,14,14,14,13,13,13,13,13,13,13,13,13,12,12,12,12,12}

　となります。各同値類の使用可能数から、これ以外の選び方はありません。

　ただし、12点の同値類は8個あるため、パネルの選び方は12の同値類の入れ替えを考慮し8C5=8C3=56通りとなります。

③について、②で算出した同値類の組から、1つを-1するように、下位の同値類と入れ替えを行います。

　13点～15点の同値類は使い切っているため、以下の2通りがあります。

　{15,14,14,14,14,13,13,13,13,13,13,13,13,13,12,12,12,12,11}(12を11に)

　{15,14,14,14,14,13,13,13,13,13,13,13,13,12,12,12,12,12,12}(13を12に)

この操作を繰り返してS-pを求めます。

Sに近いパネル群を探索しているときほど最高得点の可能性は高いわけですから、

結果S-pの値も狭まる可能性が高くなります。

したがってSから探索を開始するのは非常に有効だと考えられます。

今日はここまで。