Alas, for poor timing...

[Jacob Fugal]

Here's my actual final version with some cruft and typos cleaned up
(didn't affect accuracy, nor speed by much) and the debugging
statements removed:

-------------------------------

def knapsack(target, list)
  $cache ||= {}
  $cache[[target, list].inspect] ||= uncached_knapsack(target, list)
end

def uncached_knapsack(target, list)
  return 0, [] if target <= 0 or list.empty?

  best_value = 0
  best_list = []

  list.each_with_index do |e, i|
    next if e > target

    sublist = list.clone
    sublist.delete_at(i)
    subvalue, sublist = knapsack(target - e, sublist)

    value = subvalue + e
    if value > best_value
      best_value = value
      best_list = sublist + [e]
    end
  end

  return best_value, best_list
end

ARGF.each do |line|
  credit, *lends = line.chomp.split.map{ |x| x.to_i }
  lends.sort!
  value, list = knapsack(credit, lends)
  puts list.join(' ')
end

-------------------------------

Jacob Fugal