ARC073 D Simple Knapsack ~ナップサックにおける全探索の亜種~

ナップサック問題に制約、 $N \leqq 100、w_1 \leqq w_i \leqq w_1+3$

Wがばかでかいので当然普通のdpではMLEする。

ここでＮが小さいときに注目、Ｎが小さいときにうまくいくのは全探索、全列挙的な手法となる。

100では全列挙は厳しいけど、ここで、重さは４通りしかない！ことに気づくと、

４通りでそれぞれ使う個数を全探索すればおｋ。

具体的には重さa ,a+1 ,a+2 ,a+3 でそれぞれ、p, q, r, s このものを使うとする。

それぞれの重さに関しては価値が高い順に物を選べばよい。

このとき、全探索のたびに価値や重さの合計を求めるので、累積和を使えば少し計算量が軽くなる。

ちなみに、価値が数通りしかないときでも、それぞれの価値のものの使う個数を全探索で決め打ちして、それぞれの価値の中で軽い順にとればほぼ同様に実装できる。

～まとめ～

ナップサックの全探索のパターン(いまのところ)

・　半分全列挙( $N\leqq 40$ のサイズで)　計算量は $O(2^{N/2}N)$

・　普通に使うか使わないかの探索、たぶん半分全列挙の下位互換計算量は $O(2^N)$

・　重さor価値がたかだか数通りしかないことを利用して、その数通りの個数を決め打ちしてなぐる。<-New!

以上

Senの競技プログラミング備忘録