1d Array - determine the best container size with minimal waste

Question

EDIT: Thanks Alain for the correct description for this:

The problem is this: a store that is trying to find the optimal size of its cardboard boxes in order to be able to pack all the goods and try to minimize the wasted space in the boxes.

I currently have a dataset with volumes. I need to find out if, for example, the number of containers I can use is 5, what are the 5 best sizes for all of these volumes? For example, this array contains my volume:

var numbers =[10, 20, 20, 30, 50, 50, 50, 80]; 

And to make it simple, I have 2 containers. Each of them has a size of 50 and 80.

10 is suitable at 50, but the waste is 40. 20 is also suitable at 50, but the waste is 30 and so on. 50 fits in 50, but the waste is 0. The same goes for 80. In total, the waste is 120.

But what if the sizes were different? 60 and 80. Then the total amount of waste will be 180.

 (60-10) + (60-20) + (60-20) + (60-30) + (60-50) + (60-50) + (60-50) + (80-80) 

My question is: what is the most efficient way to determine how large the sizes are for containers? Given that you know how many containers you can use, and the numbers (in this case it was volume) in the array.

So, for example, that if I didn’t know that the sizes of my container should be 50 and 80. How would I calculate the best right size if I only know how many containers I can use and how much volume of each object

Is there any algorithm for this, and if so, can you give an example? I tried looking for things like bunker packaging, a backpack and k-tools, but I don’t really understand how I can apply them to this problem. I just want to calculate which sizes are best for storing all volumes with minimal waste.

I hope that I was clear with this example, if I do not ask more. Thanks in advance.

Answer 1

This can be optimally solved in O (kn ^ 2) and O (kn) space for n elements and k container sizes using dynamic programming :

 perl -le '$b = shift; @x = @ARGV; sub f { my ($n, $k) = @_; return 0 if $n == 0; return 1e9 if $k == 0; if (!defined $m[$n][$k]) { my ($t, @best) = (0, 1e9, 0); for (my $i = $n - 1; $i >= 0; --$i) { $t += $x[$n - 1] - $x[$i]; my $y = $t + f($i, $k - 1); if ($y < $best[0]) { @best = ($y, $i); } } $m[$n][$k] = [@best]; } return $m[$n][$k][0]; } print "Cost: ", f(@x + 0, $b); my $i = @x; for (my $j = $b; $j > 0; --$j) { print $x[$i - 1]; $i = $m[$i][$j][1]; }' 2 10 20 20 30 50 50 50 80 Cost: 120 80 50 

Space usage can be further reduced to O (n) with a different rating order. The first argument is the number of containers, and the rest are the sizes of the elements in non-decreasing order. I found that the author’s question and comments are extremely confusing, despite attempts at clarification from other users, so I don’t feel too bad to let him translate this from Perl to Javascript.