Ruby and a Math Problem

Let's say I开发者_StackOverflow have to have a cart with a subtotal of 1836.36. I must achieve this exact amount by adding up several products from a list with a range of prices.

Say, I have a few products at 9.99, 29.99, 59.99 and I can add several of each to meet the desired subtotal. How would one approach this problem using Ruby?

I've thought of feeding the list of prices into a script and somehow getting the script to add until it reaches the subtotal and then spit out the prices required to reach the subtotal... just not sure how to approach it.

Any suggestions are welcome and thanks in advance. Looking forward to ideas.

---

9.99*x + 29.99*y + 59.99*z = 1836.36

brute force iterate through all the permutations of x,y,z within a range of integers

For example:

(0..9).each do |x|
  (0..9).each do |y|
    (0..9).each do |z|
       puts "x #{x} y #{y} z #{z}" if (x * 9.99 + y * 29.99 + z * 59.99 == 1836.36)
    end
  end
end

discard any answer whose sum is not 1835.36.

Something like that... haven't tested it. You could probably tweak and optimize it to ignore cases that would certainly fail to pass.