Luke Blanshard wrote:
> 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
>
>
>
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