Alas, for poor timing...

[Jacob Fugal]

Well, I fear I won't make it into round 3 of the contest. For those
that are interested, here is my solution to the final knapsack
problem:

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?
  $indent ||= 0
  puts "#{" " * $indent}Trying to fit #{list.inspect} into #{target}..."
  $indent += 1

  best_value = 0
  best_list = []

  list.each_with_index do |e, i|
    next if e.nil? or 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

  $indent -= 1
  puts "#{" " * $indent}Decided on #{best_list.inspect} for #{best_value}"
  return best_value, best_list
end

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

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

Unfortunately, at the end of time, I hadn't added the sort on the
initial list + caching. The lack of caching caused it to spiral into
recursive madness. I knew about caching, but didn't have time to
implement it before the time was up. My final solution that was
submitted had a minor bug in it as well: rather than deleting the
candidate from the sublist, I just assigned it to equal target. I
figured this would cause the short circuit on that element in the
recursion without the overhead of deleting an element from the array.
Oops, it should have been set to target + 1 since if the weight/cost
were initially 0 that would allow it to be reconsidered in the
recursion. Oops.

I just wanted to show here that Ruby *can* handle it though with
proper pruning (caching). This version works on the real input in a
matter of seconds. My submitted version couldn't even finish before I
had to submit the code.

Jacob Fugal