Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Challenge: Twist On Bin Packing

by japhy (Canon)
on Apr 07, 2006 at 16:30 UTC ( [id://541899]=note: print w/replies, xml ) Need Help??


in reply to Challenge: Twist On Bin Packing

I think you can always get a most-bins solution by putting as many of the smallest elements in one bin, and then moving on to the next, recursively. (2,2,3), (4,5), (6), (7) is the result for the set you've given.

Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart

Replies are listed 'Best First'.
Re^2: Challenge: Twist On Bin Packing
by Limbic~Region (Chancellor) on Apr 07, 2006 at 16:33 UTC
    japhy,
    I am working on a brute force implementation so that people can test their theories. It isn't as easy as I thought it might have been.

    Update: As pointed out by Anonymous Monk later in this thread with a bin size of 10 and an input list of 1,1,1,2,2,3,4,6,7,7 - this method fails

    Cheers - L~R

      Here's my brute-forcer:
      sub bin { my ($size, @set) = @_; my $best = []; my @bins; _bin($size, \@set, \@bins, 0, $best); print "BEST: <@{[ map qq{[@$_]}, @$best ]}>\n"; } sub _bin { my ($size, $set, $bins, $i, $best) = @_; if (@$set == 0) { @$best = map [@$_], @$bins if @$bins > @$best; return; } my $rem = $size - sum($bins->[$i]); for (sort { $set->[$b] <=> $set->[$a] } grep { $set->[$_] <= $rem } +0 .. $#$set) { my $n = splice @$set, $_, 1; push @{ $bins->[$i] }, $n; _bin($size, $set, $bins, (sum($bins->[$i]) == $size) ? $i+1 : $i, +$best); _bin($size, $set, $bins, $i+1, $best) if 0 == grep { $set->[$_] <= + ($rem-$n) } 0 .. $#$set; pop @{ $bins->[$i] }; pop @$bins if @{ $bins->[$i] } == 0; splice @$set, $_, 0, $n; } } sub sum { my $s = 0; $s += $_ for @{ $_[0] }; $s; }

      Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
      How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://541899]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2024-03-28 09:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found