Here's some code using randomizations and a modified "best fit" algorithm. It enforces the 900 cap, but still ignores the 840 minimum (mostly out of necessity). The naïve approach above has better load balance than I have been able to achieve here (and is also simpler and faster).
Update: Added some more packing algorithms (though, "next fit" and "worst fit" are unlikely to produce any results)
#!/usr/bin/perl
use strict; use warnings; use 5.010;
use POSIX 'ceil';
use List::Util qw/ sum shuffle min /;
my @a = sort { $b <=> $a } qw(
121 182 111 160 105 113 121 97 123 157 133 161 141 135 137 145 133 1
+37
151 118 126 141 174 181 154 109 198 114 122 162 91 99 116 122 195 19
+9 150
192 163 88 112 157 182 210 124 105 144 166 144 257 164 156 173 154 1
+93
142 143 126 118 130 107 86 131 154 131 147 134 118 115 135 141 158 1
+29
143 126 128 134 129 167 130 135 117 127 146 96 117 99 99 139 152 149
+ 136
105 124 136 160 160 139 177 115 123 103 150 183 132 171 121 114 111
+113
131 144 122 141 111 139 145 109 114 122 103 160 153 147 172 155 122
+296
124 112 161 124 311 99 157 122 120 198 152 140 162 177 98 138 156 17
+7 103
180 187 173 150 135 168 132 196 112 195 126 113 116 105 116 151 216
+188
158 121 166 148 132 89 197 92 115 98 130 103 120 261 143 126 167 203
+ 95
165 129
);
my $MAX_ITEMS = 6;
my $bins = try_hard( ceil(@a/6), 900, \@a, \&pack_best_fit, 5000 );
show_bins( $bins );
sub min_bin {
min(map sum(@$_), @{$_[0]})
}
sub show_bins {
my $bins = shift;
my $i = 1;
for (@$bins) {
my $size = sum @$_;
say "Bin $i ($size): @$_";
$i++;
}
}
sub try_hard {
my ($bins, $size, $data, $sub, $attempts) = @_;
my $best;
my $max;
for (1..$attempts) {
my $new = $sub->($bins, $size, $data);
next unless @$new == $bins;
my $test = min_bin($new);
next if $max and $test <= $max;
$best = $new;
$max = $test;
} continue { @$data = shuffle @$data }
return $best;
}
sub pack_best_fit {
my ($n, $size, $data) = @_;
my @bins = map [], 1..$n;
our @free = map $size, 1..$n;
for my $item (@$data) {
my $i = [-1, 1+$size];
for (0..$#free) {
next unless $free[$_] >= $item and @{$bins[$_]} < $MAX_ITEMS;
@$i = ($_, $free[$_]) if $free[$_] < $$i[1];
}
$i = $$i[0];
if ($i >= 0) {
push @{$bins[$i]}, $item;
$free[$i] -= $item;
} else {
push @bins, [$item];
push @free, $size-$item;
}
}
return \@bins;
}
sub pack_next_fit {
my ($n, $size, $list) = @_;
my @bins = ([]);
my $free = $size;
for my $item (@$list) {
if ($free >= $item and @{$bins[-1]} < $MAX_ITEMS) {
push @{$bins[-1]}, $item;
$free -= $item;
} else {
push @bins, [$item];
$free = $size-$item;
}
}
return \@bins;
}
sub pack_first_fit {
my ($n, $size, $list) = @_;
my @bins = ([]);
my @free = ($size);
for my $item (@$list) {
my $i;
for (0..$#free) {
if ($free[$_] >= $item and @{$bins[$_]} < $MAX_ITEMS) {
$i = $_;
last;
}
}
if (defined $i) {
push @{$bins[$i]}, $item;
$free[$i] -= $item;
} else {
push @bins, [$item];
push @free, $size-$item;
}
}
return \@bins;
}
sub pack_worst_fit {
my ($n, $size, $data) = @_;
my @bins = map [], 1..$n;
our @free = map $size, 1..$n;
for my $item (@$data) {
my $i = 0;
for (1..$#free) { $i = $_ if $free[$_] > $free[$i]; }
if ($free[$i] >= $item and @{$bins[$i]} < $MAX_ITEMS) {
push @{$bins[$i]}, $item;
$free[$i] -= $item;
} else {
push @bins, [$item];
push @free, $size-$item;
}
}
return \@bins;
}
|