php - 如何更好地将包裹(重量)分装到不同的卡车上以实现最佳效率

Question

我正在尝试通过 PHP 将重量分配给卡车。

条件

• 卡车可以有不同的尺寸
• 可设置单辆或多辆
• 卡车越少越好

我有这个

class VehicleCalculation
{
  /**
   * @var int $weight
   */
  private $weight;
  /**
   * @var array $vehicleConfig
   */
  private $vehicleConfig;

  /**
   * VehicleCalculation constructor.
   *
   * @param int $weight
   * @param array $vehicleConfig
   */
  public function __construct(int $weight, array $vehicleConfig)
  {
    $this->weight = $weight;
    $this->vehicleConfig = $vehicleConfig;
  }

  /**
   * Calculates number of vehicles by weight
   *
   * @return array
   */
  public function calculate()
  {
    $numberOfTrucks = count($this->vehicleConfig);

    // Create basement for trucks with empty array
    $base = [];
    for ($n = 0; $n < $numberOfTrucks; $n++) {
      $base[$n] = 0;
    }

    $i = 0;
    // Fill the trucks
    while ($this->weight >= 0) {

      // Iterate over weight and add it to containers, if exceeds fill the smallest one
      if ($this->weight >= $this->vehicleConfig[$i]) {
        $base[$i] += 1;
        $this->weight = $this->weight - $this->vehicleConfig[$i];
      } else {
        $base[array_keys($base)[count($base) - 1]] += 1;
        $this->weight = $this->weight - end($this->vehicleConfig);
      }
      $i++;

      if ($i >= $numberOfTrucks - 1) {
        $i = 0;
      }
    }

    return $base;
  }

}

用法

$weight = 5678;
$trucks = [1200, 600, 300];

$vehicleCalculation = new VehicleCalculation($weight, $trucks);
$result = $vehicleCalculation->calculate();

print_r($result);

最佳输出是数组[1200 => 4, 600 => 1, 300 => 1]

我的代码输出是 [1200 => 3, 600 => 3, 300 => 1] 它在重量方面是“正确的”但效率不高，因为“卡车越少越好” .

有什么办法可以让卡车的任意组合更好地分流吗？

卡车可以这样设置:

[1200, 600, 300](示例)

[2400,300]

[1600, 950, 150]

[2400]

Answer 1

工作 demo

逻辑已更新(已调试)，我快速运行了一些测试，它似乎产生了符合所需结果的正确结果。

/**
 * Find the lowest number of trucks to transport freight with a certain weight.
 * 
 * The function returns the composition and number of each type of truck
 * necessary to transport the total freight (weight). The algorithm
 * starts from the biggest type truck and works its way down to the smallest,
 * ensuring a minimum number of trucks is employed to carry the freight.
 *
 * @param int $weight       : the weight to be transported by the trucks
 * @param array $trucks     : each element is a truck-type (weight capacity)
 * @param int $sensitivity  : higher values for 'fewer trucks',
 *                            lower values for higher capacity efficiency.
 * @return array            : truck-count per type and remaining weight
 */
function optimize(int $weight = 0, array $trucks = [], $sensitivity = 10): array
{
    $weightStore = $weight; // cache weight

    // sort truck-type array (highest to lowest weight capacity). 
    rsort($trucks);

    /* initialize truckCount at 0 for all types */
    foreach ($trucks as $type) {
        $truckCount[$type] = 0;
    }

    foreach ($trucks as $type) {
        $capacity = $type; // truck capacity
        $exact = ($weight / $type);
        $round = (int) (floor($exact)); // whole trucks

        if ($exact >= 1) {
            $truckCount[$type] = $round; // whole trucks

            // adjust weight
            $weight = $weight - ($round * $type);
        }
    }

    // do we still have remaining weight
    if ($weight > 0) {
        rsort($trucks);
        foreach ($trucks as $type) {
            $ratio[$type] = $weight / $type;
            $max = max($ratio);
        }
        $type = array_search($max, $ratio);
        $truckCount[$type]++;
        $weight -= $type; // final weight adjustment
    }

    /* 
     * use the ratio of truck capacities to identify
     * edge cases in results array:
     * e.g.: algorithm selected two trucks of 300 cap
     *       where 1 of 600 cap would be more efficient.
     */
    $ratioCap = [];
    foreach ($trucks as $key => $type) {
        if (isset($trucks[$key + 1])) {
            $ratioCap[$trucks[$key + 1]] = ($trucks[$key] / $trucks[$key + 1]);
        }
    }

    /* edge cases - force fewer trucks */
    $sensitivity = ($sensitivity <= 0) ? 10 : $sensitivity; // set default if neg. or 0
    foreach ($trucks as $cycle) {
        foreach ($truckCount as $type => $number) {
            foreach ($ratioCap as $key => $value) {
                if ($type == $key && $number >= (floor($value) / $sensitivity) && $number != 1) {
                    $truckCount[$type] = 0; // group of smaller type trucks = 0
                    $truckCount[$type * $value] += 1; // the group of smaller trucks is moved into one larger truck
                }
            }
        }
    }

    /* truck capacity vs. weight transported */
    $capacityUse = 0;
    foreach($truckCount as $type => $number) {
        $capacityUse += $type * $number;
    } $weight = $weightStore - $capacityUse;

    return ['trucks' => $truckCount, 'remaining weight' => $weight];
}

注意:逻辑从最大的卡车类型开始，一直向下到更小的类型(如果可用)。卡车类型 $type 是卡车的容量(例如本例中的 1200、600 或 300)。数组 $trucks 中的每个元素代表具有一定容量(它可以承载的重量)的卡车类型。

我们首先计算所需的某种类型卡车的确切数量，$exact[$type]，但由于我们无法计算出在高速公路上行驶的卡车的“分数”，因此我们将这个数字四舍五入向下到下一个最小整数 - 使用 floor()。它将 $type 卡车的总数存储在 $truckCount[$type] 中。

返回的数组包含运输重量所需的每种类型卡车的数量 - key trucks - 以及显示剩余重量 - key remaining weight，在此示例中为 -22(如果最后一辆卡车有一些备用容量，则为负数；如果最后一辆卡车恰好装满了剩余重量，则为 0)。

边缘情况: 该算法的工作原理是装满“整辆”卡车，然后转移到下一辆较小型的卡车， 直到总重量分配到卡车上。

那么如果我们的权重是1700 和三种卡车类型 [1200, 600, 300]？逻辑选择 1 卡车 1200 容量， 0 辆 600 辆 容量的卡车(因为我们只需要这辆卡车的部分容量)，以及 2 辆 300 辆 容量的卡车。 这个结果不符合“最小卡车数量”的条件。

因此我们需要调整结果，将 2 辆 300 辆卡车替换为 1 辆 600 辆卡车。

编辑: 引入了一个“敏感度”变量作为函数参数 - 它允许算法在“卡车较少”的情况下增加“权重”。你不需要触及这个变量，但如果你想玩它，为更少的卡车设置更高的值，或者为更高的“空间效率”结果设置更低的值。默认为 10。

“调整”是在函数的末尾进行的——一个有效的代码块， 但我认为有必要在某个时候将其重构到主要逻辑中。