ナップサック問題(Ruby)

次のような問題があるとします。

学校でクラブ活動をするのに、選んだクラブの人数の合計が 150人以下になるようにするとします。クラブの想定人数とそれが使う敷地面積は次のように与えられています。
20170526161808
クラブを幾つか適当に選ぶとき、必要な敷地面積の総和の最大値を求めなさい。

 
Ruby で解いてみました。総当り法でも解けますが、動的計画法を使いました。

number = [40, 30, 24, 20, 14, 16, 15, 40, 10, 12]
square = [11000, 8000, 400, 800, 900, 1800, 1000, 7000, 100, 300]

area = Array.new(151, 0)
for i in 0..9
  tmp = area.dup
  area.each_with_index do |sq, j|
    next if sq.zero?
    index = j + number[i]
    next if index > 150
    a = sq + square[i]
    tmp[index] = a if a > tmp[index]
  end
  tmp[number[i]] = square[i] if square[i] > tmp[number[i]]
  area = tmp
end
puts area.max

答えは 28800平方メートルになります。
 

 
 

追記

配列ではなくハッシュを使うべきかも知れません。この程度ならそれほど実行時間に差はでませんが。

number = [40, 30, 24, 20, 14, 16, 15, 40, 10, 12]
square = [11000, 8000, 400, 800, 900, 1800, 1000, 7000, 100, 300]

area = {}
for i in 0..9
  tmp = area.dup
  area.each do |num, sq|
    index = num + number[i]
    next if index > 150
    a = sq + square[i]
    tmp[index] = a if !tmp[index] or a > tmp[index]
  end
  tmp[number[i]] = square[i] if !tmp[number[i]] or square[i] > tmp[number[i]]
  area = tmp
end
puts area.values.max