On Mon, 06 Feb 2006 06:16:39 -0000, Patrick Deuster <pdeuster / gmx.net>  
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:
>
> "An equivalent problem is this: given a set of integers and an integer
> /s/, does any subset sum to /s/? Subset sum can also be thought of as a
> special case of the knapsack problem
> <http://en.wikipedia.org/wiki/Knapsack_problem>."
>
> I've solved this problem before, so I'm sure it's the subset sum problem.
>

(Total non-mathematician about to butt in)

I had a look at this quiz but didn't get chance to have a go, and although  
I originally figured it'd be a subset-sum thing, I realised that  
everyone's share will be one of the partitions of (total / number of  
guys), right? I ported a fast partition algorithm and was going to try  
attacking it that way but I just didn't get the chance.

Something like,

	+ Quit if treasure_sum % guys != 0
	+ each = treasure_sum / guys
	+ parts = partition(each)
	+ have each guy try to take a partition from the treasure,
	  removing the taken treasure.

I think it gets problematic at that last step, because I think it's  
possible for the first guy to take a combination that makes sure the  
second guy can't be satisfied, while if the first guy had taken a  
different combination (say, a 2 instead of two 1s) then guy two (needing a  
1) could have been satisfied. Maybe sorting the treasure would fix that  
but I can't be certain.

Maybe not a good plan but it'd have been interesting to see if it worked...

-- 
Ross Bamford - rosco / roscopeco.remove.co.uk