simple knapsack

knapsack1.rb

s = [2,3,5,6]
k = 16

def knapsack(s, k)
  # 記録用配列を初期化
  s_size = s.size
  wmax = k
  t = Array.new(s_size).map{Array.new(wmax,Array.new())}

  for i in 0..(s_size-1) do
    for j in 0..wmax do
      if j >= s[i]
        if i == 0 # 1行目
          t[i][s[i]] = [i]
        else
          # 2行目以降
          if t[i-1][j-s[i]]
            t[i][j] = t[i-1][j-s[i]] + [i]
          else
            t[i][j] = [i]
          end
        end
      end
    end
  end
  t
end

t=knapsack(s,k)

for i in 0..3 do
  p "#{s[i]}:#{t[i]}"
end

p t.any?{|row| row[k]} ? "exist" : "not exist"