I had a small chat with Manuel Kasten, who found out that my version
can't split all loots correctly.
For example, my old version didn't split
ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46
But it's possible to split this loot to:
1: 7 78 80
2: 30 45 90
3: 19 70 76
4: 46 54 65
5: 21 34 43 67
6: 19 20 56 70
Here's my second attempt. It should now split all loots correctly.
It now remembers splits that didn't result in a complete solution and trys again.
I also added some comments, so it's easier to understand the code I use.
And because I had problems with Thunderbird wrapping the lines wrong I attached my program to the email, too. Just in case 
loot.rb (2.5 KB)
···
----------------
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, avoid=Array.new
@target,@numbers,@avoid = target, numbers,avoid.compact.uniq
end
def solve
solver @numbers.map { |n| [n] }
end
def solver paths
new_paths = Array.new # New paths will be stored here
paths.uniq.each do |path| # For each path do
return path if path.sum == @target && (!@avoid.include?path) # If it's a valid soulution and shouldn't be avoided return in
@numbers.uniq.each do |n| # Add each number to the path
# If we have numbers left to add to the path and the sum will not get greater then the target we want
if (path.count(n)<@numbers.count(n)) && (path.sum+n <= @target)
# Store the new path in our new new_path array if it shouldn't be avoided
new_path = path.dup
new_path << n
unless @avoid.include?new_path
new_paths << new_path unless new_path.sum == @target
return new_path if new_path.sum == @target
end
end
end
end
return nil if new_paths.empty? # We walked the whole tree and no new path has been found, return nil
solver new_paths # Launch again with the new paths
end
end
def find_split fair_split,loot,avoid=Array.new
current_loot = loot.dup # Remember the loot before a split has been made
stakes = Array.new
# Try splitting the loot
begin
stake = Knapsack.new(fair_split,loot,avoid).solve
stakes << stake
stake.each { |s| loot.delete_one!(s) } unless stake.nil? # Remove from the loot what has been found
end until stake.nil? || loot.empty? # Loop until the loot is empty, or the algorithm found no valid solution
if loot.empty? # The whole loot is empty, a fair split has been found
return stakes
else
if current_loot == loot # The algorithm splitted nothing, it's not possible to fairly split the loot
return nil
else # The algorithm splitted something, but it wasn't correct. Try again avoiding the already found solutions
return find_split(fair_split,current_loot,stakes+avoid)
end
end
end
adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }
fair_split = loot.sum/adventures
stakes = (loot.sum%adventures).zero? ? find_split(fair_split,loot) : nil
if stakes.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