From: "avi.bryant@..." <avi.bryant@...>
Date: 2006-02-06T19:53:21+09:00
Subject: Re: Splitting the Loot (#65)


Chris Parker wrote:
> 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.

Unfortunately there are cases where the greedy algorithm fails.  Try
this set of arguments:

3 3 3 3 2 2 2 2 2 2 2 2 2

The correct answer is:

1: 3 2 2 2
2: 3 2 2 2
3: 3 2 2 2

But the greedy algorithm get stuck at:

1: 3 3 3

Cheers,
Avi