How to better split packages (weight) to different trucks to achieve best efficiency

Question

I'm trying to split weight to trucks via PHP.

Conditions

• Trucks can be different sizes
• Single truck or multiple can be set
• The fewer trucks are better

I have this

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;
  }

}

Usage

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

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

print_r($result);

Optimal output is array [1200 => 4, 600 => 1, 300 => 1]

My code output is [1200 => 3, 600 => 3, 300 => 1] it's "correct" in the way of weight but not efficient due to "fewer trucks are better".

Is there any way how to achieve better splitting for any combination of trucks?

Trucks can be set like this :

[1200, 600, 300] (in example)

[2400,300]

[1600, 950, 150]

[2400]

Answer 1

Working demo

The logic is updated(debugged), I've quickly run some tests, and it seems to yield correct results in line with the required outcome.

/**
 * 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];
}

Note: The logic starts with the largest truck-type and works its way down to ever smaller types (if available). The type of truck, $type, is the capacity of a truck (e.g. 1200, 600, or 300 in this example). Each element in array $trucks represents a truck-type with a certain capacity(weight it can carry).

We first calculate the exact number of trucks of a certain type needed, $exact[$type], but as we cannot have 'fractions' of trucks driving down our highways, we round this number down to the next lowest integer - using floor(). It stores the whole number of trucks of $type in $truckCount[$type].

The returned array contains the number of each type truck needed to transport the weight - key trucks -, and it also shows the remaining weight - key remaining weight, which is -22 in this example (negative in case the last truck has some spare capacity, or 0 if the last truck is exactly filled with the remaining weight).

Edge cases: The algorithm works of the logic of filling 'whole' trucks, and then move on to the next, smaller type truck, untill the total weight is distributed over the trucks.

So what happens in case we have a weight of e.g. 1700 and three truck types [1200, 600, 300]? The logic selects 1 truck of 1200 capacity, 0 trucks of 600 capacity (because we'd only need part of the capacity of this truck), and 2 trucks of 300 capacity. This result would not comply with the condition of 'minimum amount of trucks'.

We therefore need to adjust the result and replace the 2 trucks of 300 capacity with 1 of 600 capacity.

EDIT: Introduced a 'sensitivity' variable as a function parameter - it allows the algorithm to put more 'weight' on the 'fewer trucks' condition. You don't need to touch this variable, but if you want to play with it, set this value higher for fewer trucks, or lower for a higher 'space efficiency' outcome. It defaults to 10.

The 'adjustment' is made at the end of the function - a code block that works, but one that I believe deserves to be refactored into the main logic at some point.