本文探讨在给定一组特定数值中，如何找出构成目标数值的因子组合，或在无法精确构成时，找出近似度最高的单个因子及其倍数。文章首先分析了简单贪婪法的局限性，随后提出了一种优化方案，通过计算每个候选因子与目标值的匹配度（余数和倍数），并进行排序，以找到最优的近似匹配。
1. 问题背景与挑战
在软件开发中，我们经常面临需要从预定义的一组离散数值中，找出若干个数值的组合，使其总和尽可能接近或等于一个目标值。例如，假设我们有一组固定的商品价格或尺寸（如700、800、900、950、1000、1100、1200、1300），现在需要为总金额3500找到一个由这些尺寸组成的方案（如1200、1200、1100）。如果无法精确构成，则需要找到一个最小余数的近似方案。
一个常见的直觉性方法是采用贪婪策略：总是优先使用当前最大的可用数值来填充目标金额。然而，这种方法往往无法得到全局最优解，尤其是在追求最小余数或特定组合时。
2. 贪婪法的局限性分析
让我们通过一个PHP代码示例来理解贪婪法的局限性。假设目标金额为 3000，可选因子数组 $sizes 包含降序排列的数值。
<?php
$amount = 3000; // 目标金额
// 可选的构成因子，通常贪婪法会从大到小处理
$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700);
$result = array(); // 存储分解结果
foreach ($sizes as $size) {
// 计算当前size能包含多少次
$count = floor($amount / $size);
if ($count > 0) {
$result[$size] = $count;
$amount -= $count * $size; // 从总金额中减去已使用的部分
}
}
echo '<pre>'; print_r($result); echo '</pre>';
?>对于 $amount = 3000，上述代码的输出将是：
立即学习“PHP免费学习笔记（深入）”；
Array
(
[1300] => 2
)分析：
- 程序首先处理 1300，3000 / 1300 取整为 2。
- $result 中记录 1300 * 2，剩余金额 $amount 变为 3000 - 2600 = 400。
- 接下来遍历 1200, 1100, ...，但由于剩余的 $amount (400) 小于所有后续的 size，因此无法再进行分配。
最终结果是 1300 * 2 = 2600，余数为 400。然而，我们很容易发现一个更优的方案：1000 * 3 = 3000，余数为 0。这清晰地表明，简单的贪婪法并不能保证找到最佳的构成方案，尤其是在追求最小余数时。它在每一步做出的局部最优选择，可能导致全局非最优的结果。
3. 优化方案：单个因子近似匹配与排序
为了克服贪婪法的局限性，特别是当我们的目标是找到一个单个候选因子，通过倍数最接近目标值，且余数最小的方案时，可以采用以下策略：
- 独立评估每个候选因子： 对于 sizes 数组中的每一个 size，独立计算它能包含在目标金额 $amount 中多少次 (times)，以及此时的余数 (remainder) 是多少。
- 构建详细结果集： 将每个 size 及其对应的 times 和 remainder 封装成一个结构（例如关联数组），并收集到 evaluated_results 数组中。
- 排序以找到最优解： 对 evaluated_results 数组进行排序。主要排序依据是 remainder（升序，即余数越小越好）。如果 remainder 相同，则可以根据 times 进行二次排序（例如，times 越少可能意味着更简洁的方案，或者根据具体业务需求决定升序或降序）。
下面是实现此优化方案的PHP代码：
<?php
$amount = 3000; // 目标金额
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ]; // 可选的构成因子
$evaluated_results = []; // 用于存储每个因子的评估结果
foreach ($sizes as $size) {
// 计算当前size能包含在amount中的次数
$times = (int)floor($amount / $size);
// 计算此时的余数
$remainder = $amount - $times * $size;
// 将结果添加到数组中，包含因子值、使用次数和余数
$evaluated_results[] = [
'size' => $size, // 当前因子值
'times' => $times, // 因子被使用的次数
'remainder' => $remainder // 剩余的金额（余数）
];
}
// 使用 usort 对结果进行自定义排序
// 排序规则：首先按 'remainder' 升序排列（余数越小越好）
// 如果 'remainder' 相同，则按 'times' 升序排列（使用次数越少越好）
usort($evaluated_results, static function ($item1, $item2): int {
$comparison = $item1['remainder'] <=> $item2['remainder']; // 比较余数
// 如果余数相同，则进行二次比较：比较使用次数
return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});
echo '<pre>'; print_r($evaluated_results); echo '</pre>';
?>4. 结果分析与解读
运行上述优化后的代码，对于 $amount = 3000，输出结果如下：
Array
(
[0] => Array
(
[size] => 1000
[times] => 3
[remainder] => 0 // 最优结果：余数为0，且使用次数为3
)
[1] => Array
(
[size] => 950
[times] => 3
[remainder] => 150 // 次优结果：余数150，使用次数3
)
[2] => Array
(
[size] => 700
[times] => 4
[remainder] => 200 // 余数200，使用次数4
)
[3] => Array
(
[size] => 900
[times] => 3
[remainder] => 300 // 余数300，使用次数3
)
[4] => Array
(
[size] => 1300
[times] => 2
[remainder] => 400 // 余数400，使用次数2
)
[5] => Array
(
[size] => 1200
[times] => 2 // 余数600，使用次数2
[remainder] => 600
)
[6] => Array
(
[size] => 800
[times] => 3 // 余数600，使用次数3（与上一个余数相同，但使用次数更多，故排在后面）
[remainder] => 600
)
[7] => Array
(
[size] => 1100
[times] => 2
[remainder] => 800 // 余数800，使用次数2
)
)从排序后的结果可以看出：
- 数组的第一个元素 [0] 提供了最优的匹配方案：使用 1000 这个因子 3 次，总和为 3000，余数为 0。这正是我们期望找到的完美匹配。
- 后续的元素则按余数从小到大排列，提供了次优的近似匹配方案。例如，950 * 3 = 2850，余数 150。
- 当余数相同时（如 1200 * 2 和 800 * 3 都产生 600 的余数），二次排序规则（这里是按 times 升序）决定了它们的相对位置。1200 * 2 (使用2次) 排在 `800 *
