Re: partition of an array

[f00li5h]

sort it and stuff the biggest one into each half...

#! /usr/bin/perl -wT 
use warnings;
use strict;

my @kitties = sort qw/ 1 2 3 4 5 9  10 /;

my $i;
my (@first, @second);
while (@kitties){
    push @first, shift @kitties;
    push @second, shift @kitties;
}

use Data::Dumper;
print Dumper (\@first, \@second );

use List::Util qw[ sum ];

print "we have ", sum( @first ), " and ", sum( @second );

Output

$VAR1 = ['1','2','4','9'];
$VAR2 = ['10','3','5',undef];
we have 16 and 18

this puts undefs in if there is an uneven number of elements (as this code shows)

[Corion]

This approach is suboptimal for the following sample case:

my @kitties = qw/1 1 1 2 2 2 2 4/;

In this example, the greedy approach will fail, producing

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

while the best solution would be

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

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

[f00li5h]

Does not.

Output:

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

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 ;)