in reply to Re: Bin packing problem variation repost (see[834245])
in thread Bin packing problem variation repost (see[834245])

I haven't run your code, but as I see no reference to either 840 or 900 within it, I somehow think you missed some of the requirements?


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
RIP an inspiration; A true Folk's Guy
  • Comment on Re^2: Bin packing problem variation repost (see[834245])

Replies are listed 'Best First'.
Re^3: Bin packing problem variation repost (see[834245])
by duelafn (Parson) on Apr 16, 2010 at 12:26 UTC

    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; }

    Good Day,
        Dean

Re^3: Bin packing problem variation repost (see[834245])
by duelafn (Parson) on Apr 16, 2010 at 12:02 UTC

    No, I saw those. I just chose to ignore them :) ... In particular, I did some additional tests using randomization with the traditional bin packing algorithms and found that the less-packed bins were typically filled to only 760 or so. Additionally, since sum(@a)/31 = 851.7, strictly enforcing the 840-900 limits is difficult/unlikely. Thus, I took the 840-900 limits to really mean "as balanced as possible", hence my solution.

    Good Day,
        Dean