From: Brian Candler <b.candler@...>
Date: 2008-11-06T01:04:56+09:00
Subject: Re: Combination of numbers in an array that add up to x

This isn't a very good solution - it probably doesn't handle cases where 
they are multiple ways to reach the same subtotal - but it is good 
enough to solve your particular problem.

BAG = [2429.63, 497.87, 51.96, 59.43, 138.4, 66.22, 28.74, 1.75, 
2075.13,
       556.14, 112.56, 116.5, 84.41, 55.97, 139.07, 24.46]
TGT = 3435.78

seen = {0 => true}
work = {0 => BAG}    # total => [remaining items]

until work.empty?
  new_work = {}
  work.each do |tot, bag|
    bag.each_with_index do |item,i|
      nt = tot + item
      next if nt > TGT || seen[nt]
      nb = bag.dup
      nb.delete_at(i)
      if nt == TGT
        puts "Items NOT in the result set:"
        p nb
        puts "If there are no duplicates, the result set is:"
        p BAG - nb
        exit
      end
      seen[nt] = true
      new_work[nt] = nb
    end
  end
  work = new_work
end
puts "Sorry, go home"
-- 
Posted via http://www.ruby-forum.com/.