简化"Bin Packing Problem"，以合并/求和一维数组中的数字条目，每个元素具有指定的上限

Question

我想要得到值的总和，并用最大值限制它们。我的最大值是500。

我的数组:

array:11 [
0 => 100
1 => 100
2 => 100
3 => 100
4 => 100
5 => 100
6 => 300
7 => 300
8 => 300
9 => 300
10 => 300
11 => 300
12 => 300
13 => 300
14 => 300
15 => 300
]

所以每个100将被加起来等于500，最后得到下面这个数组。

所需输出:

array:11 [
0 => 300
1 => 300
2 => 300
3 => 300
4 => 300
5 => 300
6 => 300
7 => 500
8 => 500
9 => 500
]

这是我目前所做的。尝试使用usort从低到高对所有数字进行排序。

usort($orderSumArr, function ($a, $b) {
return $a > $b;
});
$sumArr = [];
$current = 0;
foreach ($sumArr as $num) {
if ($current + $num <= 500) { // limit up to 500
$current += $num;
} else {
$sumArr[] = $current;
$current = $num;
}
}
$sumArr[] = $currentSum2;

这是我得到的输出。它最终将前100个加起来，结果是500，其余100个加起来是300，结果是400。

array:11 [
0 => 300
1 => 300
2 => 300
3 => 300
4 => 300
5 => 300
6 => 300
7 => 300
8 => 300
9 => 400
10 => 500
]

Answer 1

"装箱问题"有多种理论解。有些以牺牲结果的准确性为代价来优化计算效率。最可靠的算法对资源的要求很高。一种成本较低的方法是"首次拟合递减"。策略。您期望的输出比经典任务更简单，因为您希望得到合并的总和，而不是在每个bin中单独保存每个项目。

代码(演示):

function consolidate(array $array, int $capacity = 500): array
{
rsort($array);

$bins = [0];
foreach ($array as $value) {
foreach ($bins as &$bin) {
if ($capacity >= $bin + $value) {
$bin += $value;
continue 2;
}
}
$bins[] = $value;
}

return array_values(array_filter($bins));
}
var_export(consolidate($array));

为了获得最佳结果，如果您有可用的资源，请生成所有可能组合的详尽列表，并选择元素最少的组合。