|
|
| |
Algorithm::BinPack(3) |
User Contributed Perl Documentation |
Algorithm::BinPack(3) |
Algorithm::BinPack - efficiently pack items into bins
"Algorithm::BinPack" efficiently packs items
into bins. The bins are given a maximum size, and items are packed in with as
little empty space as possible. An example use would be backing up files to
CD, while minimizing the number of discs required.
my $bp = Algorithm::BinPack->new(binsize => 4);
$bp->add_item(label => "one", size => 1);
$bp->add_item(label => "two", size => 2);
$bp->add_item(label => "three", size => 3);
$bp->add_item(label => "four", size => 4);
for ($bp->pack_bins) {
print "Bin size: ", $_->{size}, "\n";
print " Item: ", $_->{label}, "\n" for @{ $_->{items} };
}
- new
- Creates a new "Algorithm::BinPack"
object. The maximum bin size is specified as a named argument 'binsize',
and is required. A fudge factor may be specified as a named argument
'fudge'. If a fudge factor is specified, item sizes will be rounded up to
a number divisible by the fudge factor. This can help keep items with
similar sizes in order by their labels.
my $bp = Algorithm::BinPack->new(binsize => 4);
my $bp = Algorithm::BinPack->new(binsize => 100, fudge => 10);
- add_item
- Adds an item to be packed into a bin. Required named arguments are 'label'
and 'size', but any others can be specified, and will be saved. An
optional 'bin' argument can be used to manually put an item into the
specified bin.
$bp->add_item(label => 'one', size => 1);
$bp->add_item(label => 'two', size => 2, desc => 'The second numeral');
$bp->add_item(label => 'zero', size => 3, bin => 0);
$bp->add_item(qw(label three size 3));
$bp->add_item(qw(label four size 4 random key));
- prefill_bin
- (Deprecated method) "add_item" now knows
how to handle the 'bin' argument directly, so this method is
redundant.
- pack_bins
- Packs the items into bins. This method tries to leave as little empty
space in each bin as possible. It returns a list of hashrefs with the key
'size' containing the total bin size, and 'items' containing an arrayref
holding the items in the bin. Each item is in turn a hashref containing
the keys 'label', 'size', and any others added to the item. If a fudge
factor was used, each item will contain a key 'fudgesize', which is the
size this item was fudged to.
for my $bin ($bp->pack_bins) {
print "Bin size: ", $bin->{size}, "\n";
for my $item (@{ $bin->{items} }) {
printf " %-6s %-20s\n", $_, $item->{$_} for keys %{ $item };
print " ---\n";
}
}
This module implements the bin packing algorithm described in 'The Algorithm
Design Manual' by Steven S. Skiena.
This module is similar to Algorithm::Bucketizer, but has a few key
differences. The algorithms in Algorithm::Bucketizer are based on
optimization by multiple iterations, so the module is set up differently. By
contrast, the algorithm used in Algorithm::BinPack is predictable, and does
not require multiple iterations. The name also reflects the well-known name
of the problem. Searching for variations on "bin packing" finds
more relevant results than variations on "bucketizer".
Carey Tilden <revdiablo@wd39.com>
Andrew 'Terra' Gillespie <algorithm_binpack@Tech.FutureQuest.net> -
"prefill_bin"
Copyright (C) 2004-05 by Carey Tilden
This code is dual licensed. You may choose from one of the
following:
- http://creativecommons.org/licenses/by/1.0
- A Creative Commons license that allows free use, while requiring
attribution.
- http://d.revinc.org/pages/license
- The I Really Could Care Less About You Public License.
Hey! The above document had some coding errors, which are explained
below:
- Around line 214:
- You forgot a '=back' before '=head1'
Visit the GSP FreeBSD Man Page Interface. Output converted with ManDoc. |