Finding "best fit" subset of a set?

Quote:

> I'd like to find a function/module which will, given an array of

> integers, return the subset of them whose sum is closest to a

> specified "target" value.

This is the knapsack problem. As far as we know, there's no algorithm

that will give you the best subset without trying all combinations.

The simplest algorithm to solve the problem is a greedy one.

#!/usr/bin/perl -w

#

# greedy algorithm to solve knapsack problem

#

$sum = 0;

if ($sum + $elt <= $max) {

$sum += $elt;

}

Quote:

}

print "Sum: $sum\n";

__END__

This goes through the list of objects, from biggest to smallest, and

adds the current object to the knapsack if it fits. It's not hard to

find situations where the greedy solution doesn't do what you wanted:

Finding 12 from 4 3 3 3 3

Sum: 10

Set: 4 3 3

It could have filled the knapsack exactly by taking the four threes,

but it was greedy and took a four, which meant it could then only make

a total of ten using the remaining threes.

There is also an approximate algorithm, in which you quantize your

file sizes, provide a lower bound for file size, and then solve this

approximation of your problem. You can find it in the lecture notes

for CS651 ("Advanced Algorithms") online at

http://www.cs.umd.edu/~samir/cs651.ps

You'll want pages 70 on.

Cheers;

Nat