PHP实现多规格线缆切割组合求最小模值方案问询

问题需求 #

• 总线缆长度 $total_length = 15，需切割为2种及以上不同长度的等长段，目标是找到模值（总长度与切割后总长度的差值绝对值）最小的切割组合
• 现有动态数组$tabl_new，当前示例结构（长度为2）：

  $array_rws = intval(count($tabl_new)); // 获取数组长度
  

  数组内容：

  array (size=2) 
    0 => 
    array (size=6)
      'cable_length' => float 0.6 
      'pieces' => int 0 
      'modulo' => float 0 
    1 => 
    array (size=6) 
      'cable_length' => float 1.6
      'pieces' => int 0
      'modulo' => float 0
  

• 核心逻辑：通过公式 x₁*l₁ + x₂*l₂ + ... + xₙ*lₙ ≈ L 求解各线缆段的数量x，填充数组的pieces字段，计算并填充modulo字段
• 需支持3种及以上线缆规格的场景，避免嵌套循环的混乱，最终将数组按modulo字段升序排序

解决方案 #

1. 精度处理优化 #

由于涉及小数计算，先将所有长度转换为整数（如乘以10，将单位转为0.1米），避免浮点数运算带来的精度误差。

2. 多规格组合求解逻辑 #

采用递归遍历替代嵌套循环，自动处理任意数量的线缆规格，同时加入剪枝优化提升效率，确保只保留模值最小的组合。

3. 代码实现示例 #

<?php
$total_length = 15; // 总线缆长度
$tabl_new = [
    ['cable_length' => 0.6, 'pieces' => 0, 'modulo' => 0],
    ['cable_length' => 1.6, 'pieces' => 0, 'modulo' => 0],
    // 可添加更多线缆规格
];

// 处理浮点数精度：转成整数计算（单位：0.1米）
$scaled_total = $total_length * 10;
$scaled_cables = array_map(function($item) {
    return ['length' => $item['cable_length'] * 10, 'original' => $item];
}, $tabl_new);

$best_combinations = [];
$min_modulo = PHP_INT_MAX;

// 递归遍历所有可能的切割组合（至少选2种线缆）
function findBestCombinations($cables, $scaled_total, $current_index, $current_pieces, $current_sum, &$best_combinations, &$min_modulo) {
    // 遍历完所有线缆时校验结果
    if ($current_index === count($cables)) {
        $selected_count = count(array_filter($current_pieces, function($p) { return $p > 0; }));
        if ($selected_count >= 2) {
            $modulo = abs($scaled_total - $current_sum);
            // 更新最优组合
            if ($modulo < $min_modulo) {
                $min_modulo = $modulo;
                $best_combinations = [$current_pieces];
            } elseif ($modulo === $min_modulo) {
                $best_combinations[] = $current_pieces;
            }
        }
        return;
    }

    $max_pieces = floor($scaled_total / $cables[$current_index]['length']);
    // 尝试当前线缆的所有可能数量（0到最大可切数量）
    for ($pieces = 0; $pieces <= $max_pieces; $pieces++) {
        $new_sum = $current_sum + ($pieces * $cables[$current_index]['length']);
        // 剪枝：当前差值已大于最小模值，无需继续
        if ($new_sum - $scaled_total > $min_modulo) {
            continue;
        }
        $new_pieces = $current_pieces;
        $new_pieces[] = $pieces;
        findBestCombinations($cables, $scaled_total, $current_index + 1, $new_pieces, $new_sum, $best_combinations, $min_modulo);
    }
}

// 启动递归求解
findBestCombinations($scaled_cables, $scaled_total, 0, [], 0, $best_combinations, $min_modulo);

// 将最优组合填充回原数组（若有多个最优组合，可自行扩展逻辑）
if (!empty($best_combinations)) {
    $best_pieces = $best_combinations[0];
    foreach ($tabl_new as $index => &$item) {
        $item['pieces'] = $best_pieces[$index];
        $item['modulo'] = $min_modulo / 10; // 转回原单位
    }
}

// 按modulo升序排序数组
usort($tabl_new, function($a, $b) {
    return $a['modulo'] <=> $b['modulo'];
});

// 输出结果
print_r($tabl_new);
?>

代码说明 #

• 精度控制：通过整数运算规避浮点数误差，保证计算准确性
• 递归遍历：无需手动编写多层嵌套循环，自动适配任意数量的线缆规格
• 剪枝优化：提前终止差值过大的分支，减少无效计算
• 结果处理：自动填充最优数量与模值，最终完成数组排序

内容的提问来源于stack exchange，提问作者warningdang