在 PHP 中实现切削库存算法

Question

我需要用 php 脚本来实现切割库存问题。由于我的数学能力不是很好，所以我只是想用暴力来解决。

从这些参数开始

• $inventory 是可剪切的长度数组。
• $requestedPieces 是客户请求的长度数组。
• $solution 是一个空数组

我目前已经制定了这个递归函数来提出所有可能的解决方案：

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

我发现的最大的低效率是它会多次找到相同的解决方案，但步骤的顺序不同。

例如：

• $库存 = 数组(1.83, 20.66);
• $requestedPieces = 数组(0.5, 0.25);

该函数将提出 8 个解决方案，而它应该提出 4 个解决方案。有什么好的方法可以解决这个问题。

Answer 1

这并没有回答你的问题，但我认为值得一提：

您还有其他几种方法可以解决您的问题，而不是暴力解决。关于该主题的维基百科页面非常详尽，但我只会描述另外两个更简单的想法。我将使用维基百科术语来表示某些单词，即库存件的主控，以及所请求的件的切割。我将使用set来表示与给定母版相关的一组剪切。

第一个基于贪婪算法，包括用最大的可用切割填充集合，直到没有更多的切割可以容纳，并对每个母版重复相同的过程，为每个母版生成一个集合。

第二个更加动态：它使用递归（就像你的一样），并在递归的每一步寻找母版和剪切的剩余长度的最佳拟合，目标是在没有更多剪切可以容纳时最小化浪费的长度。

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

上面的函数应该为您提供给定主机的最佳设置。它返回一个包含 3 个值的数组：

• master 上浪费的长度
• 集合
• 剩余的削减

参数是

• 主长度，
• 要执行的剪切（必须按降序排序），
• 已安排的削减集（预先存在的集，对于每个主控的第一次调用将为空）

注意事项：这取决于大师的顺序，您当然可以编写一个函数来尝试所有相关的可能性来找到大师的最佳顺序。