部活6

部活です。

テーマは変わらず。

今までそれらしい計算式でそれらしいことを並べてさて実装、なんて言っていましたが、根本的に間違っている点があります。それは、計算を削減すべき場所です。

以前99C19*43*20!という計算式を示しましたが、いままでの枝刈りで削減しているのは第3項の20!の計算なのです。

最も量が多いパネル選択部分の99C19を減らさない限り、目に見えた計算量の減少はあり得ません。

というわけで、ここに対するアプローチを考えます。

単純に考えると、選ばれたパネルの最高得点の和が高いものから計算していけば、解にたどり着くスピードは上がるはずです。

簡単に言うと、

①各パネルの最高得点について、19枚の和が最大になるSを求める(既知)

②99枚のパネル群から最高得点の和がSになるように19枚を選んで探索を行う

③最高得点の和がS-1, S-2 ...となるように探索を続ける

④探索pにおいて、S-pが探索で得られた最高点と同値になったら探索を打ち切る

99枚のパネルから最高得点の部分和がS-pとなるような19枚のパネル群を抽出する方法については、次回考えたいと思います。