subset_sum.rb

$target = 15.05
$items = [2.25, 2.75, 3.35, 3.55, 4.20, 5.80].select{|item| item <= $target}

def main(arr) 
  (1..arr.length).each do |n|
    # this finds all combinations of subarrays http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-combination
    # given something like [1, 2, 3, 4]
    # each iteration of this loop contains something like
    # [[1], [2], [3], [4]]
    # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    # etc...
    arr.combination(n).each do |set|
      # we loop through those sets and check each possible quantity of values
      # starting with maximum number of highest priced, going to lowest number of highest priced
      if answer = check_set_recursively(set, $target)
        return answer
      end
    end
  end
end

def check_set_recursively(arr, target, starting_quantity=nil)
  quantities = []
  remaining = target

  # this is just here to allow starting_quantity param to be nil on first run
  # starting_quantity means how many of highest priced item to select
  if(!starting_quantity)
    starting_quantity = (target / arr.last).floor
  end

  # quantities will be an array of item and quantity of the item to pick
  quantities << {item: arr.last, quantity: starting_quantity}
  remaining = remaining - (starting_quantity * arr.last).round(2)

  # loop through the remaining items and figure out how many of each can be added
  arr.reverse[1..arr.length - 1].each do |item|
    if(item <= remaining)
      quantity = (remaining / item).floor
      quantities << {item: item, quantity: quantity}
      remaining = remaining - (quantity * item).round(2)
    end
  end

  if remaining == 0
    # if remainder is 0 then we have a solution
    return quantities

  # if we don't have a solution but starting_quantity is > 0
  # then we run the loop again, but select one fewer of the highest priced items
  elsif starting_quantity > 0
    return check_set_recursively(arr, target, starting_quantity -= 1)
  end
end

answer = main($items)
if answer
  puts answer
else
  puts "NO SOLUTION"
end