使用一系列分级价格按重量计算运输成本

Question

我需要根据一系列重量规则计算运输一个盒子的成本，与此类似：

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

目标是优化结果，以便以尽可能低的成本使用最少数量的规则。

对于重 47 磅的盒子，这些规则在技术上将达到以下重量：

• (1)x47
• (5-10)x5
• (10-15)x3,(1)x2
• (15-20)x3
• (15-20)x2,(10-15)x1
• (15-20)x2,(5-10)x1
• 等等

最佳/期望的定价计算为

(15-20)

10.90 美元 +

(15-20)

10.90 美元 +

(5-10)

6.25 美元 = 28.05 美元运费。这是最便宜的价格组合的总和。

首先，为了简单起见，我创建了一个中间数组（每个范围规则的上限），如下所示（1没有上限/下限，但很容易排除）：

$tiers = [
    20,
    15,
    10,
    1,
];

然后我尝试以类似于因式分解过程的方式将初始权重分配给该数组。所以一开始我完全忽略了下限，并采取了权重，即。 37.75 磅。然后，使用以下代码，我生成了每个权重层的“分解”数组：

print_r( distribute( 37.75 );

function distribute( $weight = 0 ) {
    $tiers = [1, 10, 15, 20];

    rsort( $tiers );

    foreach ( $tiers as $tier ) {
        $counters[$tier] = 0;
    }

    foreach ( $tiers as $tier ) {
        $quotient  = $weight / $tier;
        $floored   = floor( $quotient );
        $remaining = $weight - $floored * $tier;

        if ( $quotient >= 1 && $remaining > 1 ) {
            $counters[$tier] = $floored;
            $weight          = $remaining;
        } else if ( $tier == 1 ) {
            $counters[$tier] = ( $floored + 1 );
            $weight          = $weight - ( $floored + 1 ) * $tier;
        }
    }

    return $counters;
}

这方便地产生了这样的输出：

    Array (
        [20] => 1
        [15] => 1
        [10] => 0
        [1] => 3
    )

然后，我尝试了权重为 38 的相同代码，并意识到我的第一个错误...边缘情况存在一些问题，我还无法弄清楚，对于 38 来说，仍然会在 1 上添加一个

+1

-等级规则。

然后，我尝试了 47.75 磅，发现了第二个错误......正如我所说，为了简单起见，我使用了上限，这与重量的“因式分解”混淆了。因此，对于 47.75 磅，上面的代码产生如下输出：

    Array (
        [20] => 2
        [15] => 0
        [10] => 0
        [1] => 8
    )    

这是完全错误的，因为消费 1 层 8 次并不是最经济的途径。

总而言之，不幸的是，我的方法在很多方面都有缺陷。有人可以帮我找出解决这个问题的正确代码吗？

Answer 1

我发现体重范围的不一致结构很难处理，但我确切地理解为什么需要这样 - 以便正确地汇总各个体重。

我创建了一个脚本来尝试找到最便宜的资格等级，记录等级数据，从输入重量中减去范围的最大值，然后重复。这似乎适用于我创建的所有测试。

代码：（演示）

function costFromWeight($weight, array $newRules): array {
    $parsed = [];
    foreach ($newRules as $range => $cost) {
        if (sscanf($range, '%d-%d', $min, $max) === 1) {
            $default = [$min, $min, (float) $cost];
        } else {
            $parsed[]  = [$min, $max, (float) $cost];
        }
    }
    
    $result = ['cost' => 0];
    while ($weight > 0) {
        foreach ($parsed as $i => [$min, $max, $cost]) {
            if ($weight <= $max) {
                if (!$i && $weight <= $min) {  // weight is lower than lowest range, use defaults
                    [$min, $max, $cost] = $default;
                }
                break;
            }
        }
        $result[$max] = ($result[$max] ?? 0) + 1;
        $result['cost'] += $cost;
        $weight -= $max;
    }
    return $result;
}

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

foreach ([49, 47.75, 38, 35, 23, 15, 14, 10.5, 4] as $weight) {
    echo "$weight :: ";
    print_r(costFromWeight($weight, $rules));
    echo "\n---\n";
}

输出：

49 :: Array
(
    [cost] => 28.05
    [20] => 2
    [10] => 1
)

---
47.75 :: Array
(
    [cost] => 28.05
    [20] => 2
    [10] => 1
)

---
38 :: Array
(
    [cost] => 21.8
    [20] => 2
)

---
35 :: Array
(
    [cost] => 20.1
    [20] => 1
    [15] => 1
)

---
23 :: Array
(
    [cost] => 14.5
    [20] => 1
    [1] => 3
)

---
15 :: Array
(
    [cost] => 9.2
    [15] => 1
)

---
14 :: Array
(
    [cost] => 9.2
    [15] => 1
)

---
10.5 :: Array
(
    [cost] => 9.2
    [15] => 1
)

---
4 :: Array
(
    [cost] => 4.8
    [1] => 4
)

---