1d Array - determine best container size with minimum waste

Question

EDIT: Thanks Alain for a proper description for this:

The problem is this: a shop that tries to find the optimal size of their cardboard boxes, to be able to pack all goods, and trying to minimize wasted space in the boxes.

Currently I have a dataset with volumes. I need to figure out if for example the amount of containers I can use is 5, what are the 5 best sizes to fit all those 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 with the size of 50 and 80.

10 fits in 50, but the waste is 40. 20 fits also in 50, but the waste is 30 and so on. 50 fits in 50, but the waste is 0. Same holds for 80. In total the waste is 120.

But what if the sizes were different? 60 and 80. Then the total waste would 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 big the sizes should be for the containers? Given that you know the amount of how many containers you can use and the numbers(in this case it was volume) in an array.

So for example, what if I didn't knew the sizes of my container should be 50 and 80. How would I have calculated the best correct size if I only know how many containers I can use and what volume each object has?

Is there some kind of algorithm for this, and if so, can you give an example? I tried looking things up like the bin packing, knapsack and k-means but they are not very clear to me how I can apply them to this problem. I just want to calculate which sizes are best suited to store all the volumes with minimal waste.

I hope I was clear with this example, if not please ask more about. Thanks beforehand.

Answer 1

My approach would be convert the array into a set to remove duplicate(s), then convert back to an array in order to sort it. Then reverse the order so that we have the biggest size of the goodies in front. Now, pre-processing step is done.

Next step is to declare the container availability, you can see the code and modify as you wish, in my example, I'll use 3 containers (or cardboard boxes). I modified the array to test some cases.

Iterate through the reversed array that you've made, if the container size is not equal to the current goodies size AND if you still have available container size, then reduce 1 container size availability and push the size to the container list. I put try and catch just to break out of iteration once you have no container size left to check. Lastly, fill up the rest of the goodies array with the smallest container that we've got.

This algorithm will be O(number of container_avail + number of remaining_goodies) [Basically, O(n)].

var numbers = [60, 40, 20, 20, 10, 50, 50, 50, 80];
var original_numbers_length = numbers.length;
console.log('Given unsorted goodies: ', numbers);
numbers = new Set(numbers);
numbers = Array.from(numbers)
numbers.sort();
numbers.reverse();

var container_avai = 3;
var container_size = 0;
var container_list = [];

console.log('All goodies: ', numbers);
console.log('Given container available: ', container_avai);

var BreakException = {}

try{
    numbers.forEach(function(item){
    if( container_size != item && container_avai > 0){
        container_avai -= 1;
        container_size = item;
        container_list.push(container_size);
    }
    if ( container_avai == 0){
        throw BreakException;
    }
});}
catch (e) {
    // Done
}
remaining_goodies = original_numbers_length - container_list.length;
smallest_container = container_list[container_list.length - 1];

for (i = 0; i < remaining_goodies; i++){
    container_list.push(smallest_container);
}

console.log('Appropriate containers are: ', container_list);

The output I got:

Given unsorted goodies:  [ 60, 40, 20, 20, 10, 50, 50, 50, 80 ]
All goodies:  [ 80, 60, 50, 40, 20, 10 ]
Given container available:  3
Appropriate containers are:  [ 80, 60, 50, 50, 50, 50, 50, 50, 50 ]

Hope this helps.