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

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

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

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

Answer 1

对于 n 个物品和 k 个容器大小，可以使用动态规划在 O(kn^2) 时间和 O(kn) 空间内以最佳方式解决此问题：

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 并没有感到太难过。