動的計画法の学習(from:Paiza)

M = gets.to_i # プロジェクトに必要な人員数
N = gets.to_i # 下請けの会社の数

dp = Hash.new
dp[0] = 0

N.times{|i|
  line = gets.split(" ")
  num = line[0].to_i
  price = line[1].to_i
  temp_dp = dp.clone
  dp.each_with_index{|(k, v), j|
    idx = k + num # 対象のキーを求める
    min = v + price
    if dp.has_key?(idx)
      # 既に値が入っていた場合のみ、その値と比較して小さい方を格納
      min = [min, dp[idx]].min
    end
    temp_dp[idx] = min
  }
  dp = temp_dp
}
dp.select!{|k, v| k >= M}
puts dp.values.min