我需要使用 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 个解决方案。有什么好办法解决这个问题。