Sort the array and select consecutive entries until you reach the point where adding the next entry takes you over your magic number. If your sort is in ascending sequence, this gives you the most number of elements that will fit your constraint (this is the Maximize Number of Jobs Processed solution). If your sort is in descending sequence then you get the "Biggest Jobs Complete First" solution. Both solutions are local min/max solutions, and are reasonably easy to implement. Red claims that 95% of the time the effort involved in a full solution (by brute-force, since the problem is not algorithmically 'easy') is not cost-effective; i.e. the amount of improvement you get does not pay for the computing resources you consumed to get the better solution.

However neither of those solutions actualy get what the poster asked for unless i'm misunderstanding your explanation.

2 3 5 10 20
target  = 29
asc     = 2 3 5 10 = 18 distance = 11
desc    = 20 5 3   = 28 distance =  2
closest = 20 10    = 30 distance =  1

2 3 4 5 10 20
target  = 40
asc     = 2 3 4 5 10  = 24 distance = 16
desc    = 20 10 5 4   = 39 distance =  1
closest = 20 10 5 3 2 = 40 distance =  0
[download]

In both cases that algorithm failes to get the closes match. I don't have a solution so I should probably shut up, but I was curious if i missed something in your explanation, of if that is just solving a similar problem.


___________
Eric Hodges

my @values = (10,40,30,14,50,29,59,20,59,20,10,1,3,5,2,4);

use Algorithm::Bucketizer;

    # Create a bucketizer
my $bucketizer = Algorithm::Bucketizer->new(bucketsize => 291);

for my $value (@values) {

    # Add items to it
    $bucketizer->add_item($value, $value);
}

$bucketizer->optimize(maxrounds => 1000, algorithm => "brute_force");

for my $bucket ($bucketizer->buckets()) {
    my @items = $bucket->items();
    print $bucket->level(), ": @items\n";
}
[download]

1000 Rounds:

286: 4 2 5 3 1 10 20 59 20 59 29 50 14 10
70: 30 40
[download]

10,000 Rounds:

286: 4 2 5 3 1 10 20 59 20 59 29 50 14 10
70: 30 40
[download]