No Caffeine, No Life

プログラミング(主にPython)

ABC 060 D:Simple Knapsack 全探索(直積集合)、動的計画法(メモ化再帰)

問題:

D: Simple Knapsack - AtCoder Beginner Contest 060 | AtCoder

解説:

問題の解説にあるように、今回は重さの範囲が限定されている(w0 <= wi <= w0+3)ので、それを考慮すると全探索することができる。すなわち、

  • 重さは全部で4通り。
  • その4通りについて、それぞれ何個モノが与えられているかカウント (w_num)
  • 4つの場合の直積集合をとり、それらの組み合わせにおいて、重さが規定値W以下であればvの和を取り、最大値を求めていく。

 たとえば、入力例1の時、

  • w_set := 重さの候補。[2, 3, 4]。
  • w_num := #各重さの個数。[range(0,2), range(0,3), range(0,2)]のように格納(重さ2はrange(0, 2)、すなわち0個か1個選べる。重さ3はrange(0,3)、すなわち、0個、1個、2個選べる)
  • for i in product(*w_num) :=ここでiは、[range(0,2), range(0,3), range(0,2)]の直積集合ひとつひとつを表す。たとえば、(0, 1, 2) (重さ2が0個、重さ3が1個、重さ4が2個、という意味)のように。
  • zip(i, w_set) := 上記を式で書いたもの。各個数と重さをまとめてあげる。[(1, 2), (2, 3), (0, 4)]であれば、重さ2が1個、重さ3が2個、重さ4が0個。

zipをうまく使えるようになりたいなぁ。。。

動的計画法(メモ化再帰)の場合、

 

参考:

動的計画法(ナップサック問題) - アルゴリズム講習会