use strict; use warnings; my ($binsize, %n, @n, $total, $smallest, $bin, @bin, @bins); $binsize = 50; push @_, ((int rand 10) + 1) for 1..1000; my $c = 0; my $time = time(); $n{$_}++, $total += $_ for @_; while ($n{1} && $n{1} > $binsize) { push @bins, [split //, '1'x$binsize]; $n{1} -= $binsize; $total -= $binsize; } while ($total > $binsize) { @n = (); push @n, [$_, $n{$_}] for sort {$a <=> $b} keys %n; $smallest = $binsize + 1; find(\@n, 0, 0, 0, ''); $n{$_}--, $total -= $_ for @bin = split / /, $bin; push @bins, [@bin]; } $bin = ''; $bin .= "$_ "x$n{$_} for sort {$a <=> $b} keys %n; push @bins, [split / /, $bin]; for (@bins) { print "@$_\n"; } print "$c iterations in " . (time() - $time) . " seconds"; sub find { $c++; my ($n, $p, $stotal, $small, $set) = @_; my ($num, $count) = $n[$p] ? @{$n[$p]} : 0; if ($p > $#$n || $stotal + $num > $binsize) { if ($smallest > $stotal && (!$small || $stotal + $small > $binsize)) { $bin = $set; $smallest = $stotal; } return; } my $remains = $binsize - $stotal; my $max = $remains < $num * $count ? int($remains / $num) : $count; for (reverse 0..$max) { find($n, $p+1, $stotal+$num*$_, ($small || $_ == $max ? $small : $num), $set."$num "x$_); } }