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

我正在尝试通过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]

最佳答案

工作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]的卡车总数。

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

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

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

因此，我们需要调整结果，并用600个容量中的1个替换2个容量300的卡车。

编辑:引入了“敏感性”变量作为函数参数-它允许算法在“卡车数量较少”的情况下增加“重量”。您无需触摸此变量，但如果要使用它，则为较少的卡车设置此值，为更高的“空间效率”结果设置较低的值。默认为10。

在功能的末尾进行“调整”-一个有效的代码块，
但是我认为应该在某个时候将其重构为主要逻辑。

关于php - 如何更好地将包裹(重量)分配给不同的卡车以实现最佳效率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58645730/