本文探讨了如何在给定一组预设数值中，为目标数字寻找最佳的单一组成元素及其倍数，以实现最小化余数。通过分析初始贪婪算法的局限性，我们提出并实现了一种基于遍历、计算与自定义排序的优化策略，确保优先匹配无余数或最小余数的组合，从而高效地找到最接近目标值的构成方案。
在软件开发中，经常会遇到需要将一个目标数值分解为一系列预设构成元素的问题。例如，计算特定金额可以由哪些面额的钞票组成，或者一个总容量可以由哪些规格的容器填充。一个常见的挑战是，当目标数值不能被某个单一构成元素完美整除时，如何找到最接近的构成方案，即产生最小余数的方案。
问题描述与初始尝试的局限性
假设我们有一个目标金额 $amount (例如 3000)，以及一组允许的构成元素 $sizes (例如 [1300, 1200, 1100, 1000, 950, 900, 800, 700])。我们的目标是找出 $sizes 中哪个元素，通过乘以某个整数倍数，能够最接近 $amount，同时使余数最小。
一个直观但存在缺陷的初始方法是采用“贪婪算法”：从最大的构成元素开始，尽可能多地减去它，然后对剩余的金额重复此过程。
0) {
$result[$size] = $times;
$currentAmount -= $times * $size;
}
}
echo ''; print_r($result); echo '
';
?>对于 $amount = 3000，上述代码的输出将是：
立即学习“PHP免费学习笔记（深入）”；
Array
(
[1300] => 2
)这个结果表明使用了两个 1300，总计 2600，剩余 400。然而，我们可能期望得到的是使用三个 1000，总计 3000，余数为 0 的方案。这揭示了贪婪算法的局限性：它只关注当前步骤的最优选择，而可能错过全局最优解。在这种情况下，因为它优先使用了最大的 1300，导致无法发现 1000 * 3 这种更优的组合。
优化策略：全面评估与自定义排序
为了克服贪婪算法的局限性，我们需要一种方法来全面评估 $sizes 数组中的每一个构成元素，并根据其产生的余数和使用次数进行排序。核心思路是：
-
独立评估： 对 $sizes 数组中的每一个构成元素，独立计算它能被目标金额整除的次数，以及由此产生的余数。
-
结果收集： 将每个构成元素的评估结果（包括元素值、使用次数和余数）存储起来。
-
自定义排序： 对收集到的结果进行排序，优先选择余数最小的方案；如果余数相同，则进一步考虑使用次数等其他因素。
实现步骤
我们将使用 PHP 来实现这一优化策略：
- 定义目标金额和构成元素数组。
-
遍历构成元素数组： 对于每个元素，计算其能“构成”目标金额的次数 (times) 和剩余的金额 (remainder)。
-
存储评估结果： 将每个构成元素的值、计算出的次数和余数作为一个结构化数据（例如关联数组）存储到一个新的结果集中。
-
使用 usort 进行自定义排序：
-
主要排序依据： remainder (升序)，即余数越小越优先。
-
次要排序依据： 如果 remainder 相同，则根据 times (升序)，即使用次数越少越优先。这个次要排序规则可以根据具体业务需求调整，例如，如果希望在余数相同的情况下尽可能多地使用构成元素，则可以设置为降序。在我们的例子中，选择升序意味着在余数相同时，我们倾向于使用更少的构成元素。
$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 ''; print_r($evaluations); echo '
';
?>输出分析
运行上述代码，我们将得到一个按优化规则排序的结果数组：
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 的情况，并添加相应的错误处理或默认逻辑。
总结
通过对目标金额和所有可能构成元素进行全面评估，并结合自定义排序逻辑，我们能够有效地找到在给定构成元素集合中，能以最小余数（或无余数）最接近目标金额的单一构成方案。这种方法避免了贪婪算法可能导致的局部最优解问题，提供了一个更健壮和灵活的数值构成匹配策略。
