主页 / coding / 问题 / 78313988
Accepted
James B.
Asked: 2024-04-12 11:15:48 +0800 CST

将数字分配到一系列因素中（如贪心算法）

  • 772

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

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

因此，根据此数组，一个重 47 磅的盒子的运输成本为 10.90 + 10.90 + 6.25 = 28.05 美元。

这是因为 47 将消耗两倍范围 (15-20] 和一倍范围 (5-10]。(表示>方程符号， while]表示<=方程符号。

首先，为了简单起见，我创建了一个中间数组（每个范围规则的上限），如下所示（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 层规则中添加 a 。

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

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

这是完全错误的，因为 1 层不能被消耗 8 次，因为 8（或者确切地说 7.99）属于 (5-10] 范围。

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

1 个回答

  1. Best Answer

    我发现体重范围的不一致结构很难处理，但我确切地理解为什么需要这样——这样才能正确地计算出各个体重的总和。

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

    代码：（演示）

    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
)

---
    • 2

相关问题