Я искал какое-то время, чтобы попытаться найти какое-то решение для проблемы, которая в настоящее время выполняет блокировку задачи, которую я пытаюсь выполнить. Я столкнулся с несколькими решениями на других языках программирования, которые я действительно не понимаю, несмотря на мои попытки сделать это. Я также видел много терминов, связанных с этой проблемой, таких как перестановки, рефакторинг, суммы подмножества, монеты в долларах и т. Д.
Если я собираюсь сделать это неправильно, пожалуйста, не стесняйтесь, дайте мне знать.
Вот проблема в двух словах:
Учитывая набор (массив) чисел, например: 2, 3, 7, 14 , как я могу найти, какие комбинации этих чисел составляют (или равную) конкретную сумму, например: 14 .
Пример некоторых потенциальных комбинаций для приведенных выше примеров чисел:
3 + 3 + 3 + 3 + 2 7 + 3 + 2 + 2 7 + 7 14
Поскольку проблема, которую я пытаюсь решить, находится в PHP , я бы хотел, чтобы было решение, которое можно было бы предложить на этом языке. Если нет, даже если кто-то может лучше объяснить, в чем проблема, которую я пытаюсь решить, и возможные методы этого, я был бы очень благодарен.
Или, если я, возможно, пойду по этому пути неправильно, я все уши.
Чтобы генерировать ВСЕ решения, вам понадобится использовать какой-то откат, «угадать», если первое число находится в решении или нет, и рекурсивно для каждой из возможностей (необходимо суммировать результат, или это не ).
Что-то вроде следующего псевдокода:
genResults(array, sum, currentResult): if (sum == 0): //stop clause, found a series summing to to correct number print currentResult else if (sum < 0): //failing stop clause, passed the required number return else if (array.length == 0): //failing stop clause, exhausted the array return else: //find all solutions reachable while using the first number (can use it multiple times) currentResult.addLast(array[0]) genResults(array, sum - array[0], currentResult) //clean up currentResult.removeLast() //find all solutions reachable while NOT using first number genResults(array+1, sum, currentResult) //in the above array+1 means the subarray starting from the 2nd element
Вот что я до сих пор смог найти на основе отзывов и примеров Amit, а также некоторых других примеров. Пока это работает, но я не уверен на 100%.
$totals = array(); $x=0; function getAllCombinations($ind, $denom, $n, $vals=array()){ global $totals, $x; if ($n == 0){ foreach ($vals as $key => $qty){ for(; $qty>0; $qty--){ $totals[$x][] = $denom[$key]; } } $x++; return; } if ($ind == count($denom)) return; $currdenom = $denom[$ind]; for ($i=0;$i<=($n/$currdenom);$i++){ $vals[$ind] = $i; getAllCombinations($ind+1,$denom,$n-($i*$currdenom),$vals); } } $array = array(3, 5, 7, 14); $sum = 30; getAllCombinations(0, $array, $sum); var_dump($totals);