[QUIZ] Splitting the Loot (#65)

[Manuel Kasten]

My solution... very simple, recursive, no optimizations...

Hello.
Well, your solution doesn't split [34 78 21 70 45 67 70 19 90 76 54 20
30 19 80 7 65 43 56 46] 6-ways. The problem is that you can find a
combination of gems that sum up to the correct value, but make it
impossible to complete the split, whereas if you had chosen another
combination, the split would have been possible.

Manuel

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

madonion@gentoo $ ruby Matthew\ Moss.rb 6 34 78 21 70 45 67 70 19 90 76
54 20 30 19 80 7 65 43 56 46

It is not possible to fairly split this treasure 6 ways.

 

[Luke Blanshard]

It is the subset sum problem. Read the description on the site:

Why yes, I did read it, thank you very much. And of course you're
correct that it bears a strong resemblance to subset sum, and indeed
overlaps a special case of it. However, I still say it's a different
animal, for two reasons:

1. The special case it overlaps with is not NP-complete. If you have
all positive numbers, you can find a subset sum in O(n^2).

2. You aren't just finding a single subset. You are partitioning the
set into a collection of equal subsets. And since the special case is
not NP-complete, it is this partitioning that makes this problem hard.

Seems to me that this is a variant of a bin-packing problem with no
allowance for leftover space.

Luke Blanshard

 

[Patrick Deuster]

Why yes, I did read it, thank you very much. And of course you're
correct that it bears a strong resemblance to subset sum, and indeed
overlaps a special case of it. However, I still say it's a different
animal, for two reasons:

1. The special case it overlaps with is not NP-complete. If you have
all positive numbers, you can find a subset sum in O(n^2).

2. You aren't just finding a single subset. You are partitioning the
set into a collection of equal subsets. And since the special case is
not NP-complete, it is this partitioning that makes this problem hard.

Seems to me that this is a variant of a bin-packing problem with no
allowance for leftover space.

Luke Blanshard

Yes, you're right.
I realized that a few days ago and recoded my solution, because my first
one did just solve a simple subset problem and not the problem you
explained.

Patrick

 

[Manuel Kasten]

Here is my solution. It is short and simple. I take advantage of the
fact that for there to be an answer, every treasure must be used, so a
greedy algorithm that tries the highest valued treasures first works
well.

Hi.

It doesn't split

72, 49, 83, 74, 65, 81, 92, 27, 58, 12, 97, 5, 8, 1, 38, 73, 6, 13, 29,
36, 83, 65, 95, 96, 89, 55, 43, 91

8-ways


nor


62, 93, 97, 85, 31, 2, 80, 83, 76, 54, 71, 70, 74, 42, 79, 7, 14, 66, 7,
100, 88, 68, 37, 99, 47, 51, 66, 23, 80

8-ways


Manuel Kasten

 

[Dominik Bathon]

Here is my solution.

It first sorts the gems by value and then, tries to split them =20
recursively. The sorting is not necessary for split_loot to work, but it =
=20
works much faster on sorted sets.

If only a number of adventurers and no loot is given, then a random loot =
=20
is generated.

Dominik


def split_loot(cnt, gems, first_call =3D true)
return [gems] if cnt =3D=3D 1
sum =3D gems.inject(0) { |s, n| s + n }
share =3D sum / cnt
if first_call
# only do these checks once
if sum % share !=3D 0 || gems.max > share || gems.empty?
raise "impossible"
end
end
# search all subsets of the gems whose sum is share, for each try to
# split the remaining loot into cnt - 1 parts
choose_stack =3D [0]
share_sum =3D gems.first
last =3D gems.size - 1
until choose_stack.empty?
while share_sum < share && choose_stack.last < last
choose_stack << choose_stack.last + 1
share_sum +=3D gems[choose_stack.last]
end
if share_sum =3D=3D share
# recursive call
rest_gems =3D gems.values_at(*((0...gems.size).to_a - choose_stack=
))
if (res =3D split_loot(cnt - 1, rest_gems, false) rescue nil)
return (res << gems.values_at(*choose_stack))
end
end
if choose_stack.last =3D=3D last
share_sum -=3D gems[last]
choose_stack.pop
end
unless choose_stack.empty?
share_sum -=3D gems[choose_stack.last]
choose_stack << choose_stack.pop + 1
share_sum +=3D gems[choose_stack.last]
end
end
raise "impossible"
end

if $0 =3D=3D __FILE__
begin
if ARGV.size >=3D 2
cnt, *gems =3D ARGV.map { |s| Integer(s) }
else
# generate a test
cnt =3D ARGV.shift.to_i
share_sum =3D rand(1000)
gems =3D []
cnt.times {
rest =3D share_sum
while rest > 0
cur =3D rand(rest) + 1
gems << cur
rest -=3D cur
end
}
end
split_loot(cnt, gems.sort.reverse).each_with_index { |s, i|
puts "#{i+1}: #{s.join(' ')}"
}
rescue =3D> e
puts e
end
end