CODEWITHSUNDEEP
phpalgorithm
Mike
Mike

Reputation: 2900

Implementing Cutting Stock Algorithm in PHP

I need to implement the Cutting Stock Problem with a php script. As my math skills are not that great I am just trying to brute force it.

Starting with these parameters

I have currently worked out this recursive function to come up with all possible solutions:

function branch($inventory, $requestedPieces, $solution){
    // Loop through the requested pieces and find all inventory that can fulfill them
    foreach($requestedPieces as $requestKey => $requestedPiece){
        foreach($inventory as $inventoryKey => $piece){
            if($requestedPiece <= $piece){
                $solution2 = $solution;
                array_push($solution2, array($requestKey, $inventoryKey));
                $requestedPieces2 = $requestedPieces;
                unset($requestedPieces2[$requestKey]);
                $inventory2 = $inventory;
                $inventory2[$inventoryKey] = $piece - $requestedPiece;
                if(count($requestedPieces2) > 0){
                    branch($inventory2, $requestedPieces2, $solution2);
                }else{
                    global $solutions;
                    array_push($solutions, $solution2);
                }
            }
        }
    }
}

The biggest inefficiency I have discovered with this is that it will find the same solution multiple times but with the steps in a different order.

For example:

The function will come up with 8 solutions where it should come up with 4 solutions. What is a good way to resolve this.

Upvotes: 5

Views: 4761

Answers (1)

didierc
didierc

Reputation: 14730

This does not answer your question, but I thought it could be worth being mentioned:

You have several other ways to solve your problem, rather than brute forcing it. The wikipedia page on the topic is pretty thorough, but I'll just describe two others simpler ideas. I will use the wikipedia terminology for certain words, namely master for inventory piece, and cut for a requested piece. I will use set to denote a set of cuts pertaining to a given master.

The first one is based on the greedy algorithm, and consist in filling a set with the largest available cut, until no more cut may fit, and repeat that same process for each master, yielding a set for each one of them.

The second one is more dynamic: it uses recursion (like yours), and look for the best fit for the remaining length of master and cuts at each step of the recursion, the goal being to minimize the wasted length when no more cuts can fit. 

function branch($master, $cuts, $set){
     $goods = array_filter($cuts, function($v) use ($master) { return $v <= $master;});
     $res = array($master,$set,$cuts);
     if (empty($goods))
         return $res;
     $remaining = array_diff($cuts, $goods);
     foreach($goods as $k => $g){
         $t = $set;
         array_push($t, $g);
         $r = $remaining;
         $c = $goods;
         for ($i = 0; $i < $k; $i++)
             array_push($r,array_shift($c));
         array_shift($c);
         $t = branch($master - $g, $c, $t);
         array_walk($r, function($k,$v) use ($t) {array_push($t[2], $v);});
         if ($t[0] == 0) return $t;
         if ($t[0] < $res[0])
             $res = $t;
     }
     return $res;
}

The function above should give you the optimal set for a given master. It returns an array of 3 values:

  • the wasted length on master
  • the set
  • the remaining cuts

The parameters are

  • the master length,
  • the cuts to be performed (must be sorted in descending order),
  • the set of cuts already scheduled (a preexisting set, which would be empty for the first call for each master)

Caveats: It depends on the masters' order, you could certainly write a function which tries all the relevant possibilities to find the best order of masters.

Upvotes: 3

Related Questions