個数制限つき部分和問題

subset_sum_problem2.rb

## 個数制限つき部分和問題
## http://rubyfiddle.com/riddles/cffe6

n=3
a=[3,5,8]
m=[3,2,2]
K=17

dp = Array.new(K+1,-1)
dp[0] = 0

n.times{|i|
  j = 0
  while j <= K
    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
    j += 1
  end
  }

if dp[K] >= 0
  puts "Yes"
else
  puts "No"
end