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

いろいろとPaizaの課題を解いている中で、動的計画法が便利だということなので、その学習と実装を記載する。
基本的に以下の記事に記載されている内容を読んで実装しただけ。
https://paiza.jp/poh/kirishima

以下、実装。記事に記載されているコードと若干異なる部分があるが、これでも満点を取ることができた。

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

アルゴリズムになんとなく苦手意識を持っていたが、解説の記事の内容が分かりやすく、実装も思っていたよりもずっと簡単に済んだ。
地味に新しい武器を手に入れた感覚。
いつかは、A*等の高度なアルゴリズムもマスターしたいが、基本的にアルゴリズムを業務で使うことはないだろうし、結構先のことになるだろう。。。