DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Efficient Use Of Space On Multiple CDs

11.03.2009
| 1990 views |
  • submit to reddit
        <a rel="nofollow" href="http://search.cpan.org/perldoc?Algorithm%3A%3ABinPack">Algorithm::BinPack</a>
<a rel="nofollow" href="http://search.cpan.org/perldoc?Algorithm%3A%3ABucketizer">Algorithm::Bucketizer</a>
<a rel="nofollow" href="http://search.cpan.org/perldoc?Algorithm%3A%3AKnapsack">Algorithm::Knapsack</a>
<a rel="nofollow" href="http://search.cpan.org/%7Eandale/Algorithm-Knapsack-0.02/bin/filesack">http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/bin/filesack</a>
<a rel="nofollow" href="http://www.perlmonks.org/?node_id=420851">Burning ISOs to maximize DVD space</a>
<a rel="nofollow" href="http://www.perlmonks.org/?node_id=434432">How to maximise the content of my data CD</a>
<a rel="nofollow" href="http://bttb.sourceforge.net/">http://bttb.sourceforge.net/</a> (on Windows, which I'm not)
<a rel="nofollow" href="http://www.google.com/search?q=The%20Match%20Fit%20algorithm">The Match Fit algorithm</a>
<a rel="nofollow" href="http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm">Bin Packing</a>

#!/usr/bin/perl
#
#
#
use warnings;
use strict;
use Cwd;

use Algorithm::BinPack;
my $cd_size = 734003200;

my $bp = Algorithm::BinPack->new(binsize => $cd_size);

my $dir = cwd;
my %size;

opendir(DIR, $dir) || die "Can't open dir '$dir': $!\n";
for my $file ( readdir DIR ) {

    if ( -f "$dir/$file" ) {
        my $size = (stat $file)[7];
        $size{$file} = $size;
        $bp->add_item(label => "$file",   size => $size);
    }

}
closedir DIR;

for my $cd ($bp->pack_bins) {

    print "CD size: ", $cd->{size}, "\n";

    for my $file (@{ $cd->{items} }) {
        printf "  %-9s\t%-32s\n", $file->{size}, $file->{label};
    }

    print $/;

}

#!/usr/bin/perl
#
#
#
use strict;
use warnings;
use Cwd;

use Algorithm::Bucketizer;

my $cd_size = 734003200;
my $algorithm = "brute_force";
# my $algorithm = "random";
my $seconds = 1800;
my $number_of_rounds = 16777216;

my $b = Algorithm::Bucketizer->new( bucketsize => $cd_size );

my $dir = cwd;
my %size;

opendir(DIR, $dir) || die "Can't open dir '$dir': $!\n";
for my $file ( readdir DIR ) {

    if ( -f "$dir/$file" ) {
        my $size = (stat $file)[7];
        $size{$file} = $size;
        $b->add_item($file, $size);
    }

}
closedir DIR;

$b->optimize(
    algorithm  => $algorithm,
    maxtime    => $seconds,
    maxrounds  => $number_of_rounds
);

for my $bucket ($b->buckets()) {

    print "CD ", $bucket->serial(), $/;
    my $size = 0;

    for my $item ($bucket->items()) {

    print "$size{$item}\t$item\n";
    $size += $size{$item};

    }

    print "Size: $size\n\n";

}

#!/usr/bin/perl
#
#
#
use warnings;
use strict;
use Cwd;

use Algorithm::Knapsack;

my $cd_size = 734003200;

my $dir = cwd;
my %size;
my @weights;

opendir(DIR, $dir) || die "Can't open dir '$dir': $!\n";
for my $file ( readdir DIR ) {

    if ( -f "$dir/$file" ) {
        my $size = (stat $file)[7];
        $size{$size} = $file;
        push @weights, $size;
    }

}
closedir DIR;

my $knapsack = Algorithm::Knapsack->new(
    capacity => $cd_size,
    weights  => \@weights,
);

$knapsack->compute();

foreach my $solution ($knapsack->solutions()) {

    print $/;

    for my $sz ( @{$solution} ) {

        print "$weights[$sz]\t$size{$weights[$sz]}\n";

    }

}