寻找最佳数字组合的算法——装箱问题

Question

假设我有以下度量：

8018020024041050110

我可以将每个数字组合存储到每个单元最多480个。如何计算所需的最小单位数，以便以最有效的方式分布所有度量？

我已经标记了PHP，但它也可以是JS，甚至可以是伪语言。

我知道我应该告诉你我已经做了什么，但我很纠结于如何处理。首先想到的是递归，但我不是数学专家，不知道如何高效地做到这一点。。。

非常感谢您的帮助。

更详细地说：我正试图根据墙壁所需的不同长度来计算我必须订购的踢脚板数量。每个踢脚板的长度为480厘米，我想知道最好的铺设方式，所以我必须购买最少数量的踢脚板。与其说这是额外订购踢脚板，不如说这是一个有趣的谜题(至少对我来说)

使用解决方案更新

尽管人们试图结束这个问题，但我已经开始摆弄垃圾箱包装问题的描述，并遵循将所有物品从最大到最小排序的想法，然后以尽可能好的方式进行匹配。我创建了这个小类，它可能会在未来帮助其他人：

<?php
class BinPacker {
private $binSize;
public function __construct($binSize) {
$this->binSize = $binSize;
}
public function pack($elements) {
arsort($elements);
$bins = [];
$handled = [];
while(count($handled) < count($elements)) {
$bin = [];
foreach($elements as $label => $size) {
if(!in_array($label, $handled)) {
if(array_sum($bin) + $size < $this->binSize) {
$bin[$label] = $size;
$handled[] = $label;
}
}
}
$bins[] = $bin;
}
return $bins;
}
public function getMeta($bins) {
$meta = [
'totalValue' => 0,
'totalWaste' => 0,
'totalBins' => count($bins),
'efficiency' => 0,
'valuePerBin' => [],
'wastePerBin' => []
];
foreach($bins as $bin) {
$value = array_sum($bin);
$binWaste = $this->binSize - $value;
$meta['totalValue'] += $value;
$meta['totalWaste'] += $binWaste;
$meta['wastePerBin'][] = $binWaste;
$meta['valuePerBin'][] = $value;
}
$meta['efficiency'] = round((1 - $meta['totalWaste'] / $meta['totalValue']) * 100, 3);
return $meta;
}
}
$test = [
'Wall A' => 420,
'Wall B' => 120,
'Wall C' => 80,
'Wall D' => 114,
'Wall E' => 375,
'Wall F' => 90
];
$binPacker = new BinPacker(488);
$bins = $binPacker->pack($test);
echo '<h2>Meta:</h2>';
var_dump($binPacker->getMeta($bins));
echo '<h2>Bin Configuration</h2>';
var_dump($bins);

它给出一个输出：

Meta:
array (size=6)
'totalValue' => int 1199
'totalWaste' => int 265
'totalBins' => int 3
'efficiency' => float 77.898
'valuePerBin' => 
array (size=3)
0 => int 420
1 => int 465
2 => int 314
'wastePerBin' => 
array (size=3)
0 => int 68
1 => int 23
2 => int 174
Bin Configuration
array (size=3)
0 => 
array (size=1)
'Wall A' => int 420
1 => 
array (size=2)
'Wall E' => int 375
'Wall F' => int 90
2 => 
array (size=3)
'Wall B' => int 120
'Wall D' => int 114
'Wall C' => int 80

虽然数据集相对较小，但满足了相当高的低效率。但在我自己的配置中，我输入了所有的墙壁和天花板测量，我达到了94.212%的效率(n=129个测量)。

(注意：该类不检查混淆标签，因此，例如，如果您定义Wall A两次，结果将不正确。)

结论：对于天花板和墙壁踢脚线，我可以比我的手动踢脚线少订购一个，以有效地展开它们。

Answer 1

在我看来，这就像是Bin Packing Problem的一个变体，您试图选择组成480(或略低于480)的元素组合。这是一个计算上相当困难的问题，根据它需要的效率/准确性，试图获得准确的结果可能会有些过头。

一个粗略的启发式方法可能只是对度量进行排序，不断将最小的度量添加到一个单元中，直到下一个度量让你复习为止，然后添加到新的单元中并重复。