From: Niklas Frykholm <niklas@...>
Date: 2006-02-06T18:05:48+09:00
Subject: Re: [QUIZ] Splitting the Loot (#65)


> Subset Sum and Partition problem are similar, I agree that this quiz 
> is closer to a Partition problem. However, if we consider the Subset 
> Sum problem: given a set of integers and an integer k, find a subset 
> whose sum is k? We can apply a subset sum algorithm to find the 
> possible subset that sums to the fair share for the first "pirate", 
> and then work in the same way on the remaining elements for the other 
> pirates.

Not without backtracking... suppose you have the treasures [1 2 3 4 5 6] 
to be split among three pirates. If the subset sum algorithm finds the 
treasures [1 2 4] for the first pirate it is impossible to divide the 
remaining treasures [3 5 6] among the remaining two pirates even though 
there exists a valid solution [1 6] [2 5] [3 4].

// Niklas