Keeping big recursive functions to a minimum with PHP

Question

I have a specific length I am trying to fill with planks. For this i need to find the best posibility of combination of planks, using as less planks as possible with the lowest leftover from the last plank. To do this i first create a tree with all possibilities. After that i flatten the array a bit, so i have all options in a single array (removing the tree aspect). As last i walk through the array to get the result with the lowest depth and the lowest leftover. The first two steps i complete by using a recursive funtion.

Problem: With a length of 5000mm and planks of 5000mm, 4000mm and 3000mm there are 7 possibilities. When i try a length of 20000mm and planks of 2450mm, 2750mm, 3000mm, 3150mm, 3600mm, 3900mm, 4000mm, 4600mm, 4900mm and 5000mm there are a couple of billion possibilities. Using my current code i exceed the 30sec limit with php. I tried looking for a good algorithm on google to solve this problem, but i can't find a possible solution.

Does anyone know a algorithm or a solution to solve this problem? I am trying to keep the calculations on a minimum to keep the speed as fast as possible.

Create tree

public function createPossibilities($lengths, $length, $depth = 1) {
    $lengths = [2450, 2750, 3000, 3150, 3600, 3900, 4000, 4600, 4900, 5000]; // example array of all possible lengths
    $res = []; // array with all possible results

    foreach ($lengths as $l) {
        $rest = $length - $l; // calculates the rest length 
        if ($rest > 0) // check if length is complete
            $children = ['depth' => $depth, 'length' => $l, 'children' => $this->createPossibilities($lengths, $rest, ($depth +1))]; // if length is not complete, do function recursively
        else
            $children = ['depth' => $depth, 'length' => $l, 'leftover' => abs($rest)]; // if length is complete, add the leftover to the array
        $res[] = $children;
    }

    return $res;
}

Flatten tree

public function flattenArray($array, &$possibilities, $str = '') {
    foreach ($array as $element) {
        $temp = $str;
        $temp .= $element['length'] . ', '; // add length to string
        if (array_key_exists('children', $element)) { // check if element has children
            $this->flattenArray($element['children'], $possibilities, $temp); // do  function recursively for the child
        } else { 
            $temp = explode(', ', $temp); // explode the string into an array
            array_pop($temp); // remove last empty element
            $temp['depth'] = count($temp); // add the depth to the array
            $temp['leftover'] = $element['leftover']; // add the leftover to the array
            $possibilities[] = $temp; // add the possibility to the array
        }
    }
}

Get best possibility

public function getBestPossibility($options, &$liggersPerBreedte) {
    $minDepth = -1;
    $minLeftover = -1;
    foreach ($options as $option) {
        if ($option['depth'] < $minDepth || $minDepth == -1) { // check if possibility has fewest lengths
            $minDepth = $option['depth']; // put min depth to this option
            unset($option['depth']); // remove depth from option
            $minLeftover = $option['leftover']; // put min leftover to this option
            unset($optie['leftover']); // remove leftover from option
            $bestPosibility = $option; // best possibility is array with lengths
        } else if ($option['depth'] == $minDepth && $option['leftover'] < $minLeftover) { // check if depth is the same as min, but leftover is less
            unset($option['depth']); // remove depth from option
            $minLeftover = $optie['leftover']; // put min leftover to this option
            unset($optie['leftover']); // remove leftover from option
            $bestPosibility = $option; // best possibility is array with lengths
        }
    }
}

Example

$tree = createPossibilities([5000, 4000, 3000], 8000);
$possibilities = [];
$flatten = flattenArray($tree, $possibilities);
$best = getBestPossibilities($possibilities); // result: [5000, 3000]

score 1 · Answer 1 · edited May 23 '17 at 12:06

1

You can improve it when you create the possiblities in a different order, for example random order and stop at some level of recursion. Or you can use an approximation, for example bin-packing. The knapsack is a bit different problem, because it gives a weight and a cost. You can also try a dynamic programming:Dynamic programming and memoization: bottom-up vs top-down approaches and memoization.

edited May 23 '17 at 12:06

Community

1
1

answered Mar 19 '15 at 14:26

Micromega

12,486
7
35
72

Thanks! This helped me find a better way. Posted my result as an answer. – Thalsan Mar 19 '15 at 17:56
@Thalsan:If my answer is helpful please consider to accept it and/or upvote it! Thank you! – Micromega Mar 19 '15 at 17:58

Matt Ko · Answer 2 · 2015-03-20T08:33:50.513

0

What you're describing here is a special case of the Knapsack problem:
Given a set of items (in your case planks), find a collection of items so that the total weight (in your case total length of planks) is less than a given limit and that the value is as large as possible (this part doesn't exist in your example).

There are plenty of solutions to the knapsack problem (described on Wikipedia), but be careful because it is NP-complete, which means that it's pretty damn hard to solve whatever strategy you'll use.

EDIT: it's actually 'find a collection of items so that the total weight (in your case total length of planks) is more than a given limit and that the value (total number of planks) is as small as possible.'

edited Mar 20 '15 at 08:33

answered Mar 19 '15 at 12:33

Matt Ko

969
7
14

can you explain why you down-voted the answer ? Wikipedia actually explains the dynamic programming approach quite well, which is what you should use here, imo. – Matt Ko Mar 19 '15 at 16:51
"this part doesn't exist in your example". Yes it does, but the other way around. It has to be larger than a limit but the shortest solution. – Sylwester Mar 19 '15 at 22:20
tbh, I didn't understand it that way around. I'll edit the answer – Matt Ko Mar 20 '15 at 08:32

score 0 · Accepted Answer · answered Mar 19 '15 at 17:55

Thanks to the answer of Phpdna I found an easier way. Instead of walking through the lengths from smallest to biggest, I reversed them and went from biggest to smallest. The first time i reach the entire length i set the depth to max depth so the function won't loop a billion times. This seems to work perfectly and a lot faster than what I had.

    $lengths = [5800, 5150, 4900, 4600, 4300, 3950, 3650, 3050, 2750, 2450];
    $length = 10000;
    $maxDepth = ceil($length / $lengths[count($lengths) - 1]);
    $leftover = $lengths[0];
    $result = '';
    getBestPossibility($length, $lengths, $result, $leftover, $maxDepth);
    echo $result; // "5800, 4300, 100(leftover)"

public function getBestPossibility($length, $lengths, &$result, &$leftover, &$maxDepth, $depth = 1, $path = '') {        
    if ($depth <= $maxDepth) {
        foreach ($lengths as $l) {       
            if ($length - $l <= 0) {          
                $maxDepth = $depth;
                if (abs($length - $l) < $leftover) {
                    $leftover = abs($length - $l);
                    $result = $depth == 1 ? $l . ', ' . $leftover . '(leftover)' : $path . ', ' . $l . ', ' . $leftover . '(leftover)';
                }
            } else {
                $path = $depth == 1 ? $l : $path . ', ' . $l;
                $depth++;
                getBestPossibility(($length - $l), $lengths, $result, $leftover, $maxDepth, $depth, $path);
            }
        }
    }
}

Keeping big recursive functions to a minimum with PHP

3 Answers3