Возможный дубликат:
Алгоритм: извлечение подмножества на основе суммы имущества
в простом случае мы имеем массив:
{6, 1, 3, 11, 2, 5,12}
и мы хотим знать все комбинации сумму элементов, содержащихся в этом массиве, до получения 12 .
в этом случае мы получим четыре комбинации:
так, как мы можем это сделать на BASIC или PHP ?. возможно, псевдокод первым ;-).
Я искал, но там просто появилась комбинация с заданным количеством элементов.
Проблема NP-Hard . Даже если определить, есть ли ЛЮБОЕ подмножество задачи, суммируемое с нужным числом, является NP-Hard (известный как проблема суммы подмножества ), и нет никакого известного полиномиального решения.
Таким образом, вы должны искать экспоненциальное решение, например, обратное отслеживание – генерировать все возможные комбинации и проверять, являются ли они действительными.
Вы можете использовать обрезку для ускорения поиска (например, если вы создаете частичное подмножество суммы 13, нет необходимости проверять другие подмножества, которые являются суперсетями этого подмножества, поскольку они определенно не приведут к решению.
псевдокод:
findValidSubsets(sum,arr,idx,currSolution): if (sum == 0): print currSolution if (sum < 0): //trim the search, it won't be succesful return //one possibility: don't take the current candidate findPermutations(sum,arr,idx+1,currSolution) //second poassibility: take the current candidate currSolution.add(arr[idx]) findPermutations(sum-arr[idx],arr,idx+1,currSolution) //clean up before returning: currSolution.removeLast() Сложность – O(2^n) – нужно в наихудшем случае генерировать все 2 ^ n возможных подмножеств
Вызывать с findValidSubsets(desiredSum,myArray,0,[]) , где [] – пустой начальный список
используя динамическое программирование, вы можете выразить решение как
solver(sum,start_index) stop_condition_here_when sum <= 0 r=0 for i=start_index ; i < last_iddex : r += solver(sum - array[i],i+1) r += solver(sum ,i+1) return r
И добавление дополнительной memositaion также ускорит эту программу
Можешь попробовать
echo "<pre>"; $sum = 12 ; //SUM $array = array(6,1,3,11,2,5,12); $list = array(); # Extract All Unique Conbinations extractList($array, $list); #Filter By SUM = $sum $list = array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);}); #Return Output var_dump($list);
Вывод
array 0 => array 1 => string '1' (length=1) 2 => string '2' (length=1) 3 => string '3' (length=1) 4 => string '6' (length=1) 1 => array 1 => string '1' (length=1) 2 => string '5' (length=1) 3 => string '6' (length=1) 2 => array 1 => string '1' (length=1) 2 => string '11' (length=2) 3 => array 1 => string '12' (length=2)
Используемые функции
function extractList($array, &$list, $temp = array()) { if (count($temp) > 0 && ! in_array($temp, $list)) $list[] = $temp; for($i = 0; $i < sizeof($array); $i ++) { $copy = $array; $elem = array_splice($copy, $i, 1); if (sizeof($copy) > 0) { $add = array_merge($temp, array($elem[0])); sort($add); extractList($copy, $list, $add); } else { $add = array_merge($temp, array($elem[0])); sort($add); if (! in_array($temp, $list)) { $list[] = $add; } } } }
Вы можете выполнять итерацию по длине набора. На каждом шаге проверьте все подмножества длины k :
for k = 1 to size(input): foreach permutation p of length k: if sum(p) == 12: bam!