4

我需要使用 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 = array(0.5, 0.25);

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

4

1 回答 1

3

这并不能回答您的问题,但我认为值得一提:

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

第一个基于贪心算法,包括用最大的可用切割填充一个集合,直到没有更多的切割可以适合,然后对每个主控重复相同的过程,为每个主控生成一个集合。

第二个更动态:它使用递归(就像你的一样),并在递归的每个步骤中寻找最适合剩余长度的 master 和切割,目标是在没有更多切割可以适应时最小化浪费的长度.

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 上浪费的长度
  • 集合
  • 剩余的削减

参数是

  • 主长度,
  • 要执行的切割(必须按降序排序),
  • 已安排的切割集(预先存在的集,对于每个主控的第一次调用将是空的)

警告:这取决于主人的顺序,你当然可以编写一个函数来尝试所有相关的可能性来找到主人的最佳顺序。

于 2013-01-03T02:27:40.093 回答