Online PHP editor | rfc for JFc8X

<?php $weight = 5678; $trucks = [1200, 600, 300]; $result = optimize($weight, $trucks); var_dump($result); $weight = 900; $trucks = [600, 350, 100]; $result = optimize($weight, $trucks); var_dump($result); $weight = 1300; $trucks = [1200, 600, 300]; $result = optimize($weight, $trucks); var_dump($result); 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]; }

3v4l.org

Active branches

Archived branches