davis has asked for the wisdom of the Perl Monks concerning the following question:
I have a problem that I suspect has been well answered by algorithms, but the trouble is I don't have a name to put to it to search for the "best" algorithm. I suspect someone with a computer science background might Just Know(tm).
Simply put, I have a list of ~100 objects that differ wildly in sizes (they're actually subdirectories). I want to sort them into different bins (which represent the tape drives I intend to use to back them up). I've come up with the following naïve code which works, but it breaks down a bit when the directory sizes vary more.
So, is this an NP-hard problem? Does it have a name? Is there a "better" way to solve it? I've tried the rather obvious sorting by size first.
#!/usr/bin/perl use warnings; use strict; use Data::Dumper; my %bins = ( A => 0, B => 0, C => 0, D => 0, ); foreach(<DATA>) { my $line = $_; chomp $line; my ($size, $name) = split /\s+/, $line; my $least_full_bin = "A"; foreach my $bin (keys %bins) { $least_full_bin = $bin if($bins{$bin} < $bins{$least_full_bin} +) } $bins{$least_full_bin} += $size; } print Dumper(\%bins); __DATA__ 2548780 foobarbaz 16913085 foobarbaz 1898507 foobarbaz 67964007 foobarbaz 50239619 foobarbaz 90904439 foobarbaz 91859405 foobarbaz 443250331 foobarbaz 271426911 foobarbaz 466223129 foobarbaz 1020605272 foobarbaz 576517351 foobarbaz 362218227 foobarbaz 597801541 foobarbaz 396406322 foobarbaz 493933490 foobarbaz 695851994 foobarbaz 1093525924 foobarbaz 3860084060 foobarbaz 1815001219 foobarbaz 1242364290 foobarbaz 167867012 foobarbaz 5201589904 foobarbaz 4229781128 foobarbaz 1805056667 foobarbaz 5139655485 foobarbaz 5202726574 foobarbaz 947237511 foobarbaz 210571932 foobarbaz 51518 foobarbaz 2737944 foobarbaz 2686687 foobarbaz 0 foobarbaz 3 foobarbaz 1 foobarbaz 1 foobarbaz 3 foobarbaz 3 foobarbaz 0 foobarbaz 0 foobarbaz 3848 foobarbaz 1 foobarbaz 6584 foobarbaz 8879 foobarbaz 1 foobarbaz 1 foobarbaz 2031703999 foobarbaz 25614 foobarbaz 1 foobarbaz 686994 foobarbaz 2 foobarbaz 32703 foobarbaz 135867 foobarbaz 7 foobarbaz 9 foobarbaz 3148830 foobarbaz 6803655 foobarbaz 147343006 foobarbaz 57013 foobarbaz 22 foobarbaz 655127653 foobarbaz 2034016 foobarbaz 1323038 foobarbaz 26 foobarbaz 9309654 foobarbaz 11 foobarbaz 472 foobarbaz 70134007 foobarbaz 1 foobarbaz 669792 foobarbaz 296399 foobarbaz 0 foobarbaz 37 foobarbaz 1775825 foobarbaz 6499972 foobarbaz 11766 foobarbaz 1392 foobarbaz 6344 foobarbaz 10290402 foobarbaz 8529 foobarbaz 0 foobarbaz 28232823 foobarbaz 796 foobarbaz
davis