PHP: найдите два или более числа из списка чисел, которые добавляются к определенной сумме

Если вы посмотрите на алгоритм 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 возможностей. Это связано с тем, что я настроил программу тестирования на использование целых чисел вместо float. Прямое сравнение с плавающей запятой редко бывает правильным , это отличный пример: вы иногда получаете 59.959999999999 вместо 59.959999999999 и поэтому матч не будет засчитан. Итак, если я запустил код 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); 

извините за добавление нового ответа, но это полное новое решение для решения всех проблем жизни, вселенной и всего …:

 function array_sum_parts($n,$t,$all=false){ $count_n = count($n); // how much fields are in that array? $count = pow(2,$count_n); // we need to do 2^fields calculations to test all possibilities # now i want to look at every number from 1 to $count, where the number is representing # the array and add up all array-elements which are at positions where my actual number # has a 1-bit # EXAMPLE: # $i = 1 in binary mode 1 = 01 i'll use ony the first array-element # $i = 10 in binary mode 10 = 1010 ill use the secont and the fourth array-element # and so on... the number of 1-bits is the amount of numbers used in that try for($i=1;$i<=$count;$i++){ // start calculating all possibilities $total=0; // sum of this try $anzahl=0; // counter for 1-bits in this try $k = $i; // store $i to another variable which can be changed during the loop for($j=0;$j<$count_n;$j++){ // loop trough array-elemnts $total+=($k%2)*$n[$j]; // add up if the corresponding bit of $i is 1 $anzahl+=($k%2); // add up the number of 1-bits $k=$k>>1; //bit-shift to the left for looking at the next bit in the next loop } if($total==$t){ $loesung[$i] = $anzahl; // if sum of this try is the sum we are looking for, save this to an array (whith the number of 1-bits for sorting) if(!$all){ break; // if we're not looking for all solutions, make a break because the first one was found } } } asort($loesung); // sort all solutions by the amount of numbers used // formating the solutions to getting back the original array-keys (which shoud be the return-value) foreach($loesung as $val=>$anzahl){ $bit = strrev(decbin($val)); $total=0; $ret_this = array(); for($j=0;$j<=strlen($bit);$j++){ if($bit[$j]=='1'){ $ret_this[] = $j; } } $ret[]=$ret_this; } return $ret; } // Inputs $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; // Output $t=57.96; var_dump(array_sum_parts($n,$t)); //returns one possible solution (fuc*** fast) var_dump(array_sum_parts($n,$t,true)); // returns all possible solution (relatively fast when you think of all the needet calculations) 

если вы не используете третий параметр, он возвращает наилучшее (с наименьшим количеством номеров) решение в виде массива (с ключами ввода-массива) – если вы установите третий параметр true , возвращаются ВСЕ решения (для тестирование, я использовал те же цифры, что и zaf в своем посте – в этом случае есть 338 решений, найденных в ~ 10 секунд на моей машине).

EDIT: если вы получите все, вы получите результаты, упорядоченные по тому, что является «лучшим» – без этого вы получите только первое найденное решение (что не обязательно самое лучшее).

EDIT2: чтобы пролить некоторое объяснение, я прокомментировал основные части кода. если кому-то нужно больше объяснений, пожалуйста, спросите

 1. Check and eliminate fields values more than 21st field 2. Check highest of the remaining, Add smallest, 3. if its greater than 21st eliminate highest (iterate this process) 4. If lower: Highest + second Lowest, if equal show result. 5. if higher go to step 7 6. if lower go to step 4 7. if its lower than add second lowest, go to step 3. 8. if its equal show result 

Это эффективно и сократит время выполнения.

Следующий метод даст вам ответ … почти все время. Увеличьте переменную итераций по своему вкусу.

 <?php // Inputs $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; // Output $t=57.96; // Let's try to do this a million times randomly // Relax, thats less than a blink $iterations=1000000; while($iterations-->0){ $z=array_rand($n, mt_rand(2,20)); $total=0; foreach($z as $x) $total+=$n[$x]; if($total==$t)break; } // If we did less than a million times we have an answer if($iterations>0){ $total=0; foreach($z as $x){ $total+=$n[$x]; print("[$x] + ". $n[$x] . " = $total<br/>"); } } ?> в <?php // Inputs $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; // Output $t=57.96; // Let's try to do this a million times randomly // Relax, thats less than a blink $iterations=1000000; while($iterations-->0){ $z=array_rand($n, mt_rand(2,20)); $total=0; foreach($z as $x) $total+=$n[$x]; if($total==$t)break; } // If we did less than a million times we have an answer if($iterations>0){ $total=0; foreach($z as $x){ $total+=$n[$x]; print("[$x] + ". $n[$x] . " = $total<br/>"); } } ?> 

Одно из решений:

 [1] + 8.99 = 8.99 [4] + 8.16 = 17.15 [5] + 2.53 = 19.68 [6] + 0.28 = 19.96 [8] + 0.34 = 20.3 [10] + 8.24 = 28.54 [11] + 4.35 = 32.89 [13] + 1.69 = 34.58 [14] + 5.64 = 40.22 [15] + 0.27 = 40.49 [16] + 2.73 = 43.22 [17] + 1.63 = 44.85 [18] + 4.07 = 48.92 [19] + 9.04 = 57.96 

Вероятно, неэффективное, но простое решение с обратным следом

 function subset_sums($a, $val, $i = 0) { $r = array(); while($i < count($a)) { $v = $a[$i]; if($v == $val) $r[] = $v; if($v < $val) foreach(subset_sums($a, $val - $v, $i + 1) as $s) $r[] = "$v $s"; $i++; } return $r; } 

пример

 $ns = array(1, 2, 6, 7, 11, 5, 8, 9, 3); print_r(subset_sums($ns, 11)); 

результат

 Array ( [0] => 1 2 5 3 [1] => 1 2 8 [2] => 1 7 3 [3] => 2 6 3 [4] => 2 9 [5] => 6 5 [6] => 11 [7] => 8 3 ) 

Я не думаю, что ответ не так прост, как упоминал Ник. допустим, у вас есть следующие номера:

 1 2 3 6 8 

ищут 10

Решение niks сделало бы это (если я понимаю это правильно):

 1*8 = 9 = too low adding next lowest (2) = 11 = too high 

теперь он удалит большое количество и начнет снова принимать новый максимум

 1*6 = 7 = too low adding next lowest (2) = 9 = too low adding next lowest (3) = 12 = too high 

… и т. д., где идеальный ответ был бы просто 8+2 = 10 … я думаю, что единственное решение пытается всевозможную комбинацию чисел и останавливается, если найденный вами амаунт найден (или реально вычислить все , если есть разные решения и сохранить, которые использовали наименьшие числа).

EDIT: реальное вычисление всех возможных комбинаций из 21 числа закончится в реальных, реальных, реальных расчетах – поэтому должно быть какое-то «интеллектуальное» решение для добавления чисел в специальном порядке (например, один в niks post – с некоторыми улучшениями, возможно, это приведет нас к надежному решению)

Не зная, является ли это заданием домашней работы или нет, я могу дать вам некоторый псевдокод в качестве подсказки для возможного решения, отметим, что решение не очень эффективно, скорее демонстрация.

Подсказка:

Сравните каждое значение поля со всем значением поля и при каждой проверке итерации, если их сумма равна TOTAL_AMOUNT .

Псевдокод:

 for i through field 1-20 for j through field 1-20 if value of i + value of j == total_amount return i and j 

Обновить:

То, что у вас есть, – это проблема суммы подмножества , указанная в ссылке Wiki, – это псевдокод для алгоритма, который может помочь вам в правильном направлении.