Если вы посмотрите на алгоритм oezis , то сразу обнаружится один недостаток: он тратит много времени на суммирование чисел, которые, как известно, не работают. (Например, если 1 + 2 уже слишком велико, нет смысла пробовать 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ... тоже .)
Таким образом, я написал улучшенную версию. Он не использует немного магии, он делает все вручную. Недостатком является то, что для сортировки входных значений требуется (используйте rsort). Но это не должно быть большой проблемой;)
function array_sum_parts($vals, $sum){
$solutions = array();
$pos = array(0 => count($vals) - 1);
$lastPosIndex = 0;
$currentPos = $pos[0];
$currentSum = 0;
while (true) {
$currentSum += $vals[$currentPos];
if ($currentSum < $sum && $currentPos != 0) {
$pos[++$lastPosIndex] = --$currentPos;
} else {
if ($currentSum == $sum) {
$solutions[] = array_slice($pos, 0, $lastPosIndex + 1);
}
if ($lastPosIndex == 0) {
break;
}
$currentSum -= $vals[$currentPos] + $vals[1 + $currentPos = --$pos[--$lastPosIndex]];
}
}
return $solutions;
}
Модифицированная версия программы тестирования oezis (см. В конце) выводит:
possibilities: 540
took: 3.0897309780121
Так что для выполнения потребовалось всего 3,1 секунды , тогда как код oezis на моей машине выполнил 65 секунд (да, моя машина работает очень медленно). Это более чем в 20 раз быстрее !
Кроме того, вы можете заметить, что мой код нашел 540 вместо 338 возможностей. Это потому, что я настроил программу тестирования, чтобы использовать целые числа вместо числа с плавающей точкой. Прямое сравнение с плавающей запятой редко бывает правильным , это отличный пример того, почему: иногда вы получаете 59.959999999999 вместо 59.96 и, следовательно, совпадение не будет засчитано. Итак, если я запускаю код oezis с целыми числами, он также находит 540 возможностей;)
Программа тестирования:
// Inputs
$n = array();
$n[0] = 6.56;
$n[1] = 8.99;
$n[2] = 1.45;
$n[3] = 4.83;
$n[4] = 8.16;
$n[5] = 2.53;
$n[6] = 0.28;
$n[7] = 9.37;
$n[8] = 0.34;
$n[9] = 5.82;
$n[10] = 8.24;
$n[11] = 4.35;
$n[12] = 9.67;
$n[13] = 1.69;
$n[14] = 5.64;
$n[15] = 0.27;
$n[16] = 2.73;
$n[17] = 1.63;
$n[18] = 4.07;
$n[19] = 9.04;
$n[20] = 6.32;
// Convert to Integers
foreach ($n as &$num) {
$num *= 100;
}
$sum = 57.96 * 100;
// Sort from High to Low
rsort($n);
// Measure time
$start = microtime(true);
echo 'possibilities: ', count($result = array_sum_parts($n, $sum)), '<br />';
echo 'took: ', microtime(true) - $start;
// Check that the result is correct
foreach ($result as $element) {
$s = 0;
foreach ($element as $i) {
$s += $n[$i];
}
if ($s != $sum) echo '<br />FAIL!';
}
var_dump($result);