プログラミングコンテストチャレンジブック演習「個数制限付き部分和問題」

今回のお題はこちら

漸化式思いつかないよ。。精進あるのみですな。

MaxK = 17
A = [3, 5, 8]
M = [3, 2, 2]

$dp = Array.new( MaxK + 1, -1)
$dp[0] = 0
for i in 0..(A.length - 1)
  for j in 0..MaxK
    if $dp[j] >= 0
      $dp[j] = M[i]
    elsif j < A[i] || $dp[j - A[i]] <= 0
      $dp[j] = -1
    else
      $dp[j] = $dp[j - A[i]] - 1
    end
  end
end

if $dp[MaxK] >= 0
  puts "YES"
else
  puts "NO"
end