本文旨在解决如何从给定数字集合中，为目标数字寻找一个最优的单类型构成组合。针对传统贪婪算法在处理非精确整除时可能出现的局限性，我们提出一种改进方法。该方法通过独立计算每个可用构成数能提供的最大倍数及其剩余量，并对结果进行智能排序，以优先选择余数最小且使用次数合理的组合，从而实现更精准的数字分解近似。
在许多实际应用场景中，我们可能需要将一个目标数值分解为由一组预定义数值（构成数）的组合。例如，在库存管理或资金分配中，我们需要从一系列固定面额或尺寸的物品中，尽可能精确地凑出或接近一个目标总量。一个常见的挑战是，当目标数值无法被构成数精确整除时，如何找到一个“最接近”的组合，或者说，一个剩余量最小的组合。
传统贪婪算法的局限性
一种直观的解决方案是采用贪婪算法：总是优先使用当前能使用的最大构成数，并尽可能多地使用它，然后用剩余的量继续这个过程。让我们看一个PHP示例：
= $size) { $times = floor($remainingAmount / $size); $result[$size] = $times; $remainingAmount -= $times * $size; } else { $result[$size] = 0; }}echo ''; print_r($result); echo '
';?>
对于 $amount = 3000，上述代码的输出将是：
Array( [1300] => 2 [1200] => 0 [1100] => 0 [1000] => 0 [950] => 0 [900] => 0 [800] => 0 [700] => 0)
这里，1300 * 2 = 2600，剩余 400。虽然 1300 * 2 是一个有效的组合，但我们知道 1000 * 3 = 3000 是一个更好的选择，因为它没有剩余量。这表明简单的贪婪算法可能无法找到全局最优的近似解，尤其是在寻求最小余数时。其主要原因在于，贪婪算法一旦选择了一个构成数并减去了相应的量，就不会回头考虑其他可能更好的组合。
立即学习“PHP免费学习笔记（深入）”；
优化算法：基于最小余数和使用次数的排序
为了克服贪婪算法的局限性，我们可以采用一种不同的策略：不立即减少目标数值，而是针对每个可用的构成数，独立地计算它能提供的最大倍数以及此时产生的剩余量。然后，我们对这些计算结果进行排序，以找到最优的近似解。这里的“最优”定义为：首先余数最小，如果余数相同，则使用次数较少的方案（或根据具体需求选择使用次数较多的方案）。
算法步骤
遍历所有构成数： 对于给定的目标数值 $amount 和构成数数组 $sizes 中的每一个 $size。计算倍数和余数：计算当前 $size 能整除 $amount 的最大次数 ($times = floor($amount / $size))。计算此时的剩余量 ($remainder = $amount - $times * $size)。存储结果： 将 $size、$times 和 $remainder 作为一个临时结果存储起来。排序结果： 对所有临时结果进行排序。主要排序键： $remainder，按升序排列（最小余数优先）。次要排序键： $times，按升序或降序排列，具体取决于业务需求。例如，如果希望在余数相同的情况下优先选择使用次数较少的（更“紧凑”的）组合，则按升序排列。如果希望优先选择使用次数较多的（可能更“分散”的）组合，则按降序排列。在我们的示例中，我们选择升序。
PHP实现
$size, 'times' => $times, 'remainder' => $remainder ];}// 使用 usort 进行自定义排序usort($results, static function ($item1, $item2): int { // 首先按 'remainder' 升序排序 $comparison = $item1['remainder'] $item2['remainder']; // 如果 'remainder' 相同，则按 'times' 升序排序 // 这样在余数相同的情况下，会优先选择使用次数较少的方案 return $comparison === 0 ? $item1['times'] $item2['times'] : $comparison;});echo ''; print_r($results); echo '
';?>
输出分析
运行上述代码，输出结果如下：
Array( [0] => Array ( [size] => 1000 [times] => 3 [remainder] => 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] 提供了最佳结果：size 为 1000，times 为 3，remainder 为 0。这正是我们期望的 1000 * 3 = 3000 的完美组合。
值得注意的是，在 remainder 均为 600 的情况下，[5] 元素 (1200 * 2) 比 [6] 元素 (800 * 3) 靠前，这是因为我们设置了次要排序键为 times 的升序，即在余数相同的情况下，优先选择使用次数更少的方案 (2
注意事项与扩展
问题定义： 本文提供的解决方案旨在找到一个单类型构成数（例如 X * N）来最佳近似目标数值。如果您的需求是寻找多种不同类型构成数的组合（例如 A * N1 + B * N2 + C * N3）来达到目标或最小余数，那么这属于更复杂的背包问题或找零问题范畴，通常需要动态规划或回溯算法来解决。本教程的方案不适用于这类多类型组合问题。性能考量： 对于较小的构成数数组，这种遍历和排序的方法效率很高。如果构成数数组非常庞大，可能需要考虑更优化的数据结构或算法。浮点数处理： 如果目标数值或构成数是浮点数，需要特别注意浮点数比较的精度问题，可能需要使用 bcmath 扩展进行精确计算，而不是直接使用 floor 和减法。排序规则： 次要排序键（times）的选择应根据具体业务需求调整。例如，如果更倾向于使用尽可能多的构成数来分解，即使余数相同，可以将 times 设置为降序排序。无解情况： 如果目标数值为负数或构成数数组为空，代码需要添加额外的逻辑进行处理，以避免错误或产生无意义的结果。
总结
通过对每个构成数独立进行计算，并结合多级排序策略，我们能够有效地找到给定目标数值的最佳单类型构成组合，尤其是在存在非精确整除情况时。这种方法比简单的贪婪算法更具鲁棒性，能够提供更符合“最小余数”或“最接近”原则的解决方案，为资源分配、库存优化等场景提供了实用的技术支持。
以上就是PHP中优化数字构成查找：最小余数与最优单类型组合算法的详细内容，更多请关注php中文网其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1328364.html
微信扫一扫 
支付宝扫一扫 
