Finding "best fit" subset of a set? 
Author Message
 Finding "best fit" subset of a set?

I'm in the process of writing a perl script to "stage" files for writing
to a CD-ROM, and 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. In other words, given an array which contains
the sizes of a series of directories, I want it to return the subset of
those directories which most closely approximates 625 megs.

Does anyone know if a module exists that could do this? I didn't find anything
obvious on CPAN. Alternatively, could someone suggest an algorithm that I
could use to write my own?

Any suggestions, tips, pointers, or whatever, are greatly appreciated.

Thanks.

/MC

--
Matthew Cravit, N9VWG               | Experience is what allows you to




Fri, 28 Apr 2000 03:00:00 GMT  
 Finding "best fit" subset of a set?



Quote:
> I'm in the process of writing a perl script to "stage" files for writing to
> a CD-ROM, and 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. In other words, given an array which contains the sizes of a
> series of directories, I want it to return the subset of  those directories
> which most closely approximates 625 megs.
> Does anyone know if a module exists that could do this? I didn't find
> anything obvious on CPAN. Alternatively, could someone suggest an algorithm
> that I  could use to write my own?

Can't make any specific suggestion but the problem is a classic in computer
science and is usually refered to as "the bin packing problem". It may help if
you use "bin" and "packing" as keywords in your searching.

--
-----------------------------------------------------------



Sun, 30 Apr 2000 03:00:00 GMT  
 Finding "best fit" subset of a set?

Quote:



> > I'm in the process of writing a perl script to "stage" files for writing to
> > a CD-ROM, and 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. In other words, given an array which contains the sizes of a
> > series of directories, I want it to return the subset of  those directories
> > which most closely approximates 625 megs.

> > Does anyone know if a module exists that could do this? I didn't find
> > anything obvious on CPAN. Alternatively, could someone suggest an algorithm
> > that I  could use to write my own?

> Can't make any specific suggestion but the problem is a classic in computer
> science and is usually refered to as "the bin packing problem". It may help if
> you use "bin" and "packing" as keywords in your searching.

> --
> -----------------------------------------------------------


I've also heard it called the Knapsack problem.  HTH, Bill.
--

How do I set my laser printer to "stun"?



Mon, 01 May 2000 03:00:00 GMT  
 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



Mon, 01 May 2000 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. "character class ""bug""

2. Is "write FILEHANDLE" supposed to set $=

3. A better "wall", redux

4. Mail::Mailer ignores my "From" setting

5. Good method of "locking"

6. Good Book: "Advanced Perl Programming"

7. Oraperl: "set serverout on"

8. (q) how to set "From:"

9. Best way to define a "constant"?

10. Setting "-state" of Menubutton->command

11. system(("cp", "-Rf", "/tmp/a/*", "/tmp/b")); doesnt wrk

12. how to parse a "this", "that", "and the ", "other" file

 

 
Powered by phpBB® Forum Software