Some random perl code I threw together:


use Data::Dumper;
use List::Util (reduce);

@p = (580, 420, 355, 335, 275, 215);
$target = 1505;
$A[0] = [0, [], 0];
foreach $i (1 .. $target) {
    my @tmp;
    foreach $a (@A) {
	next unless defined($a);
        push @tmp, [$a->[0], $a->[1], $i];
        push @tmp, [$a->[0] + $_, [@{$a->[1]}, $_], $i] foreach (@p);
    }
    @tmp = grep({$_->[0] == $i;} @tmp);

    # ok, prefer the shortes solution for no other reason
    # than 7 times mixed fruit is so boring.
    $A[$i] = reduce { if ($a->[0] == $b->[0]) {
                          @{$a->[1]} < @{$b->[1]} ? $a : $b
                      } else {
                          $a->[0] > $b->[0] ? $a : $b 
                      }
                    } @tmp;
}
print Dumper($A[$target]);

Mixed fruit? You probally have to read this xkcd strip

Update: Changing the grep statement from testing for less than or equal to strict equality seems to be about 30 times faster with the same result.