GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  ALGORITHM::BINPACK (3)

.ds Aq ’

NAME

Algorithm::BinPack - efficiently pack items into bins

CONTENTS

SYNOPSIS

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} };
    }



METHODS

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";
        }
    }



SEE ALSO

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.

AUTHOR

Carey Tilden <revdiablo@wd39.com>

CONTRIBUTORS

Andrew ’Terra’ Gillespie <algorithm_binpack@Tech.FutureQuest.net> - prefill_bin

COPYRIGHT AND LICENSE

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.

POD ERRORS

Hey! <B>The above document had some coding errors, which are explained below:B>
Around line 214: You forgot a ’=back’ before ’=head1’
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 ALGORITHM::BINPACK (3) 2005-03-16

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.