From: Patrick Deuster <pdeuster@...>
Date: 2006-02-06T00:41:11+09:00
Subject: [QUIZ][SOLUTION] Splitting the Loot (#65)

Ok, the 48 hours passed just now and as I have to leave for a day or two 
I post my solution early.

The splitting the loot problem is actually a problem known as the 
"Knapsack problem" or the "Subset sum problem".
http://en.wikipedia.org/wiki/Subset_sum_problem

I solved the problem how I learned it at university, by walking through 
a tree.
I hand the loot and the target value over to the knapsack solver and 
remove the result from the loot until either the loot is empty or 
solving the problem failed.

Here's my complete solution:

class Array
  def sum
    inject { |s,x| s + x }
  end
  def delete_one! n
    (i = index(n)) ? delete_at(i) : nil
  end
  def count n
    inject(0) { |c,x| x == n ? c+1 : c }
  end
end

class Knapsack
  def initialize target, numbers
    @target,@numbers = target, numbers
  end
  def solve
    solver @numbers.map { |n| [n] }
  end
  def solver paths
    new_paths = Array.new
    paths.each do |path|
      return path if path.sum == @target
      @numbers.each do |n|
        unless path.count(n)>=@numbers.count(n) || path.sum+n > @target
          new_path = path.dup
          new_path << n
          new_paths << new_path
          return new_path if new_path.sum == @target
        end
      end
    end
    return nil if new_paths.empty?
    solver new_paths
  end
end

adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }
fair_split,stakes = loot.sum/adventures,Array.new

begin
  stake = Knapsack.new(fair_split,loot).solve
  stakes << stake
  stake.each { |s| loot.delete_one!(s) } unless stake.nil?
end until stake.nil? || loot.empty?

if stakes.include?nil
  puts "It is not possible to fairly split this treasure #{adventures} 
ways."
else
  stakes.size.times { |i| puts "#{i+1}: " + stakes[i].sort.join(" ") }
end