ナップサック問題（Ruby）

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

学校でクラブ活動をするのに、選んだクラブの人数の合計が 150人以下になるようにするとします。クラブの想定人数とそれが使う敷地面積は次のように与えられています。

クラブを幾つか適当に選ぶとき、必要な敷地面積の総和の最大値を求めなさい。

　
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平方メートルになります。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

　
　

追記

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

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

別解（2020/11/14）

典型的な動的計画法だとこうなります。

club = [[11000, 40], [8000, 30], [400, 24], [800, 20], [900, 14],
        [1800, 16], [1000, 15], [7000, 40], [100, 10], [300, 12]]
N = 150
C = club.size

area = Array.new(C + 1) {Array.new(N + 1, 0)}

club.each_with_index do |(square, number), i|
  (0..N).each do |num|
    if num >= number
      area[i + 1][num] = [area[i][num - number] + square, area[i][num]].max
    else
      area[i + 1][num] = area[i][num]
    end
  end
end

puts area[C][N]