Re^2: partition of an array

This approach is suboptimal for the following sample case:

my @kitties = qw/1 1 1 2 2 2 2 4/;
[download]

In this example, the greedy approach will fail, producing

[4,2,2,1], [2,2,1,1]
[download]

while the best solution would be

[4,1,1,1], [2,2,2,2]
[download]

But due to the homeworky nature of the problem I won't go into this further :)

Comment on Re^2: partition of an array Select or Download Code

Replies are listed 'Best First'.
Re^3: partition of an array by f00li5h (Chaplain) on Mar 25, 2009 at 06:44 UTC
Does not. Output: `$VAR1 = [ '1', '1', '2', '2' ]; $VAR2 = [ '1', '2', '2', '4' ]; we have 6 and 9` [download] You dropped the `sort` bit! ... some time passes ... Just snagging the biggest one and stuffing it in a sack works pretty well for the knapsack problem... and since this one was only 2 partitions it didn't do too bad ;) `@_=qw; ask f00li5h to appear and remain for a moment of pretend better than a lifetime;;s;;@_[map hex,split'',B204316D8C2A4516DE];;y/05/os/&print;`	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: partition of an array
by f00li5h (Chaplain) on Mar 25, 2009 at 06:44 UTC

Does not.

Output:

$VAR1 = [ '1', '1', '2', '2' ]; $VAR2 = [ '1', '2', '2', '4' ];
we have 6 and 9
[download]

You dropped the sort bit!

... some time passes ...

Just snagging the biggest one and stuffing it in a sack works pretty well for the knapsack problem... and since this one was only 2 partitions it didn't do too bad ;)

@_=qw; ask f00li5h to appear and remain for a moment of pretend better than a lifetime;;s;;@_[map hex,split'',B204316D8C2A4516DE];;y/05/os/&print;

[reply]
[d/l]
[select]