javascript - 一维阵列 - 以最少的浪费确定最佳容器尺寸

Question

编辑:感谢 Alain 对此的正确描述:

问题是这样的:一家商店试图找到其纸板箱的最佳尺寸，以便能够包装所有商品，并尽量减少纸箱中的浪费空间。

目前我有一个包含卷的数据集。我需要弄清楚例如我可以使用的容器数量是否为 5 个，适合所有这些体积的 5 个最佳尺寸是多少？例如，这个数组包含我的卷:

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

为了简单起见，我有 2 个容器。大小分别为 50 和 80。

10装50，废40，20装50，废30等等。 50 适合 50，但浪费为 0。同样适用于 80。总共浪费为 120。

但是如果尺寸不同呢？ 60 和 80。那么总的浪费就是 180。

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

我的问题是，确定容器大小的最有效方法是什么？假设您知道可以使用的容器数量和数组中的数字(在本例中为体积)。

例如，如果我不知道我的容器的大小应该是 50 和 80 怎么办？如果我只知道我可以使用多少个容器以及每个对象的体积是多少，我将如何计算出最佳的正确大小？

是否有某种算法，如果有，您能举个例子吗？我试着查找像 bin packing、knapsack 和 k-means 这样的东西，但我不太清楚如何将它们应用到这个问题上。我只想计算哪种尺寸最适合存储所有卷，同时浪费最少。

我希望我对这个例子很清楚，如果不明白请询问更多。提前致谢。

Answer 1

我的方法是将数组转换为一个集合以删除重复项，然后转换回数组以便对其进行排序。然后颠倒顺序，让我们有最大的好东西在前面。至此，预处理步骤完成。

下一步是声明容器可用性，您可以查看代码并根据需要进行修改，在我的示例中，我将使用 3 个容器(或纸板箱)。我修改了数组来测试一些情况。

遍历您创建的反向数组，如果容器大小不等于当前的好东西大小并且您仍然有可用的容器大小，则减少 1 个容器大小可用性并将大小推送到容器列表。一旦您没有要检查的容器大小，我就尝试和捕获只是为了中断迭代。最后，用我们得到的最小容器填充 goodies 数组的其余部分。

此算法的复杂度为 O(容器数量_avail + 数量 remaining_goodies)[基本上，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);

我得到的输出:

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 ]

希望这对您有所帮助。