今回のお題はこちら。
今回はdp用メモテーブル$dpのサイズを間違えて不具合になりました。
ナップサックに入れられる重さは0〜wなので、
配列のサイズはwじゃなくてw+1にしないといけないんですなー。
W = [2,1,3,2] #input V = [3,2,4,2] #input w = 5 #input INF = -1 $dp = Array.new( W.length ).map!{ Array.new( w + 1, INF ) } def maxValue(index, leftWeight) return $dp[index][leftWeight] unless $dp[index][leftWeight] == INF value = 0 if index == W.length - 1 value = 0 elsif W[index] <= leftWeight value = [maxValue(index + 1, leftWeight), maxValue(index + 1, leftWeight - W[index]) + V[index]].max else value = maxValue(index + 1, leftWeight) end $dp[index][leftWeight] = value return value end puts maxValue(0, w)