PHP - 根据 属性 值将对象组织成数组，直到满足条件

Question

我正在想办法编写以下代码

• 对象数组，每个对象都有一个属性表示权重
• 遍历对象并将它们分类到新数组中，每个数组包含尽可能多但不超过 X 磅。

添加项目的简单循环，当当前数组的总重量 >= X 磅时，创建一个新数组并继续，这部分很简单。但是我希望最终结果尽可能高效，这意味着每个数组包含最多可能的项目而不超过最大值。

如果我没有正确解释这一点，我深表歉意，但有人知道我在这里的意思吗？我认为我正在尝试做的事情的根源是使用数学优化对这些项目进行排序。

谢谢！

Answer 1

如 Sammitch 的 link 所述，有许多解决方案。

这是一个基本的，可能不会给出 最好的 结果，也不会是 最快的 ，但应该是一个好的开始。关键部分是在开始时按重量对它们进行排序。然后它只是循环遍历它们，测试它们是否适合当前容器，如您所说。它给了我合理的结果。

演示 link：https://3v4l.org/KWrZo

<?php

$max_weight = 100;

// init with some random weights
$objects = [];
for ($i = 1; $i <= 100; $i++) {
    $objects[] = (object) ['id' => $i, 'weight' => rand(1, 50)];
}

// sort by weight, heaviest first
usort($objects, function ($a, $b) {
    return $b->weight <=> $a->weight;
});

$containers = [];
$container_number = 0;
$total_weight = 0;

while (true) {

    $container_number++;

    $container = [];
    $container_weight = 0;

    foreach ($objects as $key => $object) {
        // add this object to the container if it won't push it over the max weight
        if ($container_weight + $object->weight <= $max_weight) {
            $container[] = $object;
            unset($objects[$key]);
            $container_weight += $object->weight;
            $total_weight += $object->weight;
            if ($container_weight == $max_weight) {
                break;
            }
        }
    }

    $containers[$container_number] = $container;
    $container_contents = count($container);

    echo 'Container #' . $container_number . ' total weight: ' . $container_weight . ' (' . $container_contents . ' items)' . PHP_EOL;

    if (empty($objects)) {
        break;
    }
}

echo 'Total weight: ' . $total_weight . PHP_EOL;

var_dump($containers);