基于阶梯重量价格数组的最优运费计算方案求解

问题背景 #

给定运费规则示例：

$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

需要根据包裹重量计算最低运费，同时优先使用最少的运输规则数量。例如47磅的包裹，最优组合是2个15-20（各$10.90）加1个5-10（$6.25），总运费$28.05。

原有仅按重量上限做因式分解的方法存在核心缺陷：

• 边缘重量处理逻辑错误（如38磅时错误给1磅规则额外加量）
• 忽略规则重量下限，导致分配出不经济的组合（如47.75磅时错误分配2个20磅加8个1磅）

解决方案代码 #

function calculateOptimalShipping($weight, $rules) {
    // 解析规则为结构化数组，包含重量区间、单价、性价比
    $parsedRules = [];
    foreach ($rules as $range => $price) {
        $price = (float)$price;
        if ($range === '1') {
            $parsedRules[] = [
                'min' => 1,
                'max' => INF,
                'price' => $price,
                'value' => 1 / $price, // 每美元覆盖的重量
                'label' => $range
            ];
        } else {
            list($min, $max) = explode('-', $range);
            $min = (float)$min;
            $max = (float)$max;
            $parsedRules[] = [
                'min' => $min,
                'max' => $max,
                'price' => $price,
                'value' => $max / $price, // 每美元能覆盖的最大重量（性价比）
                'label' => $range
            ];
        }
    }

    // 按性价比降序排序，性价比相同则优先选大区间规则（减少使用数量）
    usort($parsedRules, function($a, $b) {
        if ($a['value'] === $b['value']) {
            return $b['max'] <=> $a['max'];
        }
        return $b['value'] <=> $a['value'];
    });

    $bestCombination = [];
    $minTotalCost = INF;

    // 递归遍历所有可能组合，剪枝避免无效计算
    $findBestCombination = function($remainingWeight, $currentCombination, $currentCost, $ruleIndex) use (&$findBestCombination, $parsedRules, &$bestCombination, &$minTotalCost) {
        if ($currentCost >= $minTotalCost) return;

        if ($remainingWeight <= 0) {
            if ($currentCost < $minTotalCost) {
                $minTotalCost = $currentCost;
                $bestCombination = $currentCombination;
            } elseif ($currentCost === $minTotalCost) {
                // 成本相同时，选规则数量更少的组合
                $currentCount = array_sum($currentCombination);
                $bestCount = array_sum($bestCombination);
                if ($currentCount < $bestCount) {
                    $bestCombination = $currentCombination;
                }
            }
            return;
        }

        for ($i = $ruleIndex; $i < count($parsedRules); $i++) {
            $rule = $parsedRules[$i];
            $maxCount = ceil($remainingWeight / $rule['min']);
            $maxCount = max(1, $maxCount);

            for ($count = 1; $count <= $maxCount; $count++) {
                $newCost = $currentCost + $count * $rule['price'];
                $newCombination = $currentCombination;
                $newCombination[$rule['label']] = isset($newCombination[$rule['label']]) ? $newCombination[$rule['label']] + $count : $count;

                // 计算剩余重量：选count个规则最多能覆盖count*max重量，剩余为原重量减去该值（最小为0）
                $newRemaining = max($remainingWeight - $count * $rule['max'], 0);
                $findBestCombination($newRemaining, $newCombination, $newCost, $i);

                // 若当前数量已能覆盖剩余重量，无需尝试更多数量
                if ($count * $rule['max'] >= $remainingWeight) break;
            }
        }
    };

    $findBestCombination($weight, [], 0, 0);

    // 兜底：若未找到组合（理论上不会触发），用1磅规则补全
    if (empty($bestCombination)) {
        $count = ceil($weight);
        $bestCombination['1'] = $count;
        $minTotalCost = $count * $rules['1'];
    }

    return [
        'combination' => $bestCombination,
        'total_cost' => number_format($minTotalCost, 2)
    ];
}

// 测试示例
$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

// 测试47磅
$result = calculateOptimalShipping(47, $rules);
echo "47磅包裹最优组合：\n";
print_r($result['combination']);
echo "总运费：$" . $result['total_cost'] . "\n\n";

// 测试47.75磅
$result = calculateOptimalShipping(47.75, $rules);
echo "47.75磅包裹最优组合：\n";
print_r($result['combination']);
echo "总运费：$" . $result['total_cost'] . "\n\n";

// 测试38磅
$result = calculateOptimalShipping(38, $rules);
echo "38磅包裹最优组合：\n";
print_r($result['combination']);
echo "总运费：$" . $result['total_cost'] . "\n";

代码核心逻辑 #

1. 规则解析与排序：将字符串规则转换为结构化数据，按「每美元覆盖最大重量」的性价比降序排序，确保优先尝试最经济的规则。
2. 递归剪枝搜索：遍历所有可能的规则组合，通过剪枝跳过已超过当前最低成本的无效路径，保证效率。
3. 双重最优判断：优先选择最低运费，运费相同时选择规则数量最少的组合，满足题目双重目标。

内容的提问来源于stack exchange，提问作者James B.