本文探讨了如何在给定一组预设数值中，为目标数字寻找最佳的单一组成元素及其倍数，以实现最小化余数。通过分析初始贪婪算法的局限性，我们提出并实现了一种基于遍历、计算与自定义排序的优化策略，确保优先匹配无余数或最小余数的组合，从而高效地找到最接近目标值的构成方案。
在软件开发中，经常会遇到需要将一个目标数值分解为一系列预设构成元素的问题。例如，计算特定金额可以由哪些面额的钞票组成，或者一个总容量可以由哪些规格的容器填充。一个常见的挑战是，当目标数值不能被某个单一构成元素完美整除时，如何找到最接近的构成方案，即产生最小余数的方案。
问题描述与初始尝试的局限性
假设我们有一个目标金额 $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 数组中的每一个构成元素，并根据其产生的余数和使用次数进行排序。核心思路是：
- 独立评估： 对 $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 的情况，并添加相应的错误处理或默认逻辑。
总结
通过对目标金额和所有可能构成元素进行全面评估，并结合自定义排序逻辑，我们能够有效地找到在给定构成元素集合中，能以最小余数（或无余数）最接近目标金额的单一构成方案。这种方法避免了贪婪算法可能导致的局部最优解问题，提供了一个更健壮和灵活的数值构成匹配策略。