1d阵列 - 确定最佳容器尺寸,同时减少浪费

问题描述 投票:8回答:2

编辑:感谢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怎么办。如果我只知道我可以使用多少个容器以及每个对象有多少卷,我将如何计算出最佳的正确大小?

是否有某种算法,如果是这样,你能举个例子吗?我试着像垃圾箱包装,背包和k-means一样,但我不清楚如何将它们应用到这个问题上。我只想计算哪种尺寸最适合存储所有体积而且浪费最少。

我希望我对这个例子很清楚,如果不是,请详细询问。先谢谢。

javascript arrays algorithm containers
2个回答
0
投票

我的方法是将数组转换为一个集合以删除重复,然后转换回数组以对其进行排序。然后颠倒顺序,以便我们拥有最大尺寸的好吃的东西。现在,完成预处理步骤。

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

迭代您所做的反转数组,如果容器大小不等于当前的商品大小并且如果您仍有可用容器大小,则减少1个容器大小可用性并将大小推送到容器列表。一旦你没有要检查的容器大小,我把try和catch只是为了突破迭代。最后,用我们拥有的最小容器填充其余的goodies数组。

该算法将为O(container_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 ]

希望这可以帮助。


-1
投票

这可以使用dynamic programming在O(kn ^ 2)时间和O(kn)空间中针对n个项目和k个容器大小进行最佳求解:

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

可以使用不同的评估顺序将空间使用量进一步减少到O(n)。第一个参数是容器的数量,其余的是非递减顺序的项目大小。我发现这个问题和作者的评论非常令人困惑,尽管其他用户试图澄清,所以我不觉得让他/她将其从Perl转换为Javascript。

© www.soinside.com 2019 - 2024. All rights reserved.