Patrick Deuster wrote:
> Luke Blanshard wrote:
>> Patrick Deuster wrote:
>>> ...
>>> 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 don't believe that this problem is equivalent to the subset sum 
>> problem, because all of the numbers involved are positive.  Different 
>> animal.
> 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