优化PHP数值构成：最小化余数的元素匹配算法-php教程-PHP中文网

优化PHP数值构成：最小化余数的元素匹配算法

花韻仙語

发布： 2025-10-30 12:29:20

原创

873人浏览过

优化PHP数值构成：最小化余数的元素匹配算法

本文探讨了如何在给定一组预设数值中，为目标数字寻找最佳的单一组成元素及其倍数，以实现最小化余数。通过分析初始贪婪算法的局限性，我们提出并实现了一种基于遍历、计算与自定义排序的优化策略，确保优先匹配无余数或最小余数的组合，从而高效地找到最接近目标值的构成方案。

在软件开发中，经常会遇到需要将一个目标数值分解为一系列预设构成元素的问题。例如，计算特定金额可以由哪些面额的钞票组成，或者一个总容量可以由哪些规格的容器填充。一个常见的挑战是，当目标数值不能被某个单一构成元素完美整除时，如何找到最接近的构成方案，即产生最小余数的方案。

问题描述与初始尝试的局限性

假设我们有一个目标金额 $amount (例如 3000)，以及一组允许的构成元素 $sizes (例如 [1300, 1200, 1100, 1000, 950, 900, 800, 700])。我们的目标是找出 $sizes 中哪个元素，通过乘以某个整数倍数，能够最接近 $amount，同时使余数最小。

一个直观但存在缺陷的初始方法是采用“贪婪算法”：从最大的构成元素开始，尽可能多地减去它，然后对剩余的金额重复此过程。

<?php
$amount = 3000;
$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700); // 假设已按降序排列

$result = array();
$currentAmount = $amount; // 使用一个临时变量来保存当前待分解的金额

foreach ($sizes as $size) {
    $times = floor($currentAmount / $size);
    if ($times > 0) {
        $result[$size] = $times;
        $currentAmount -= $times * $size;
    }
}

echo '<pre>'; print_r($result); echo '</pre>';
?>

登录后复制

对于 $amount = 3000，上述代码的输出将是：

立即学习“PHP免费学习笔记（深入）”；

Array
(
    [1300] => 2
)

登录后复制

这个结果表明使用了两个 1300，总计 2600，剩余 400。然而，我们可能期望得到的是使用三个 1000，总计 3000，余数为 0 的方案。这揭示了贪婪算法的局限性：它只关注当前步骤的最优选择，而可能错过全局最优解。在这种情况下，因为它优先使用了最大的 1300，导致无法发现 1000 * 3 这种更优的组合。

优化策略：全面评估与自定义排序

为了克服贪婪算法的局限性，我们需要一种方法来全面评估 $sizes 数组中的每一个构成元素，并根据其产生的余数和使用次数进行排序。核心思路是：

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

独立评估： 对 $sizes 数组中的每一个构成元素，独立计算它能被目标金额整除的次数，以及由此产生的余数。
结果收集： 将每个构成元素的评估结果（包括元素值、使用次数和余数）存储起来。
自定义排序： 对收集到的结果进行排序，优先选择余数最小的方案；如果余数相同，则进一步考虑使用次数等其他因素。

实现步骤

我们将使用 PHP 来实现这一优化策略：

定义目标金额和构成元素数组。
遍历构成元素数组： 对于每个元素，计算其能“构成”目标金额的次数 (times) 和剩余的金额 (remainder)。
存储评估结果： 将每个构成元素的值、计算出的次数和余数作为一个结构化数据（例如关联数组）存储到一个新的结果集中。
使用 usort 进行自定义排序：
- 主要排序依据： remainder (升序)，即余数越小越优先。
- 次要排序依据： 如果 remainder 相同，则根据 times (升序)，即使用次数越少越优先。这个次要排序规则可以根据具体业务需求调整，例如，如果希望在余数相同的情况下尽可能多地使用构成元素，则可以设置为降序。在我们的例子中，选择升序意味着在余数相同时，我们倾向于使用更少的构成元素。

<?php
$amount = 3000; // 目标金额
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ]; // 允许的构成元素

$evaluations = []; // 用于存储所有构成元素的评估结果

foreach ($sizes as $size) {
  $times = (int)floor($amount / $size); // 计算该元素能使用的次数
  $remainder = $amount - $times * $size; // 计算剩余金额

  $evaluations[] = [
      'size' => $size,        // 构成元素的值
      'times' => $times,      // 使用次数
      'remainder' => $remainder // 剩余金额
  ];
}

// 使用 usort 进行自定义排序
usort($evaluations, static function ($item1, $item2): int {
  // 首先比较余数：余数小的排在前面
  $comparison = $item1['remainder'] <=> $item2['remainder'];

  // 如果余数相同，则比较使用次数：次数少的排在前面
  return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});

echo '<pre>'; print_r($evaluations); echo '</pre>';
?>

登录后复制

输出分析

运行上述代码，我们将得到一个按优化规则排序的结果数组：

Array
(
    [0] => Array
        (
            [size] => 1000
            [times] => 3
            [remainder] => 0   // 最优结果：余数为0
        )

    [1] => Array
        (
            [size] => 950
            [times] => 3
            [remainder] => 150   // 次优结果
        )

    [2] => Array
        (
            [size] => 700
            [times] => 4
            [remainder] => 200
        )

    [3] => Array
        (
            [size] => 900
            [times] => 3
            [remainder] => 300
        )

    [4] => Array
        (
            [size] => 1300
            [times] => 2
            [remainder] => 400
        )

    [5] => Array
        (
            [size] => 1200
            [times] => 2         // 与下一个元素的余数相同
            [remainder] => 600
        )

    [6] => Array
        (
            [size] => 800
            [times] => 3         // 余数相同，但使用次数更多，因此排在后面
            [remainder] => 600
        )

    [7] => Array
        (
            [size] => 1100
            [times] => 2
            [remainder] => 800
        )
)

登录后复制

从输出中可以看到，第一个元素 [0] 即为我们寻找的最佳构成方案：使用 1000 这个构成元素 3 次，恰好等于目标金额 3000，余数为 0。这正是我们希望通过优化算法找到的结果。

注意事项与扩展

单类型构成元素： 本文提供的解决方案着重于寻找“单一类型”的最佳构成元素。例如，对于 3000，它会找到 3 个 1000。如果问题要求寻找“多种类型”构成元素的组合（例如，3500 可以由 1200, 1200, 1100 组成），则需要采用更复杂的算法，如动态规划（背包问题或找零问题变种），这超出了本文的范畴。
性能考量： 对于较小的 $sizes 数组和 $amount，上述遍历和排序方法效率很高。如果 $sizes 数组非常庞大，或者 $amount 极大导致 $times 很大，可能需要考虑更优的数据结构或算法。
排序规则的灵活性： usort 中的比较函数是高度可定制的。您可以根据实际业务需求调整排序逻辑，例如，在余数相同的情况下，是优先选择使用次数多的构成元素，还是使用次数少的构成元素。
边界条件处理： 在实际应用中，需要考虑 $sizes 数组为空、$amount 为负数或小于所有 $size 的情况，并添加相应的错误处理或默认逻辑。