4

可能重复：
算法：根据属性总和提取子集

在简单的情况下，我们有一个数组：

{6, 1, 3, 11, 2, 5,12}

我们想知道该数组中包含的元素总和的所有组合，以获得12。

在这种情况下，我们将得到四种组合：

  • 12
  • 1 + 11
  • 6 + 5 + 1
  • 1 + 3 + 2 + 6

那么，我们如何在 BASIC 或 PHP 中做到这一点？也许首先是伪代码;-)。

我一直在寻找，但只是与预定数量的元素组合在一起。

4

4 回答 4

6

你可以试试

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;
            }
        }
    }
}
于 2012-10-11T11:20:14.707 回答
5

问题是NP-Hard。即使确定是否存在总和为所需数字的问题的任何子集也是 NP-Hard（称为子集和问题），并且没有已知的多项式解决方案。

因此，您应该寻找指数解决方案，例如回溯解决方案 - 生成所有可能的组合，并检查它们是否有效。

您可以使用修剪来更快地进行搜索（例如，如果您生成 sum 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 个可能的子集
Invoke with findValidSubsets(desiredSum,myArray,0,[])，其中[]是一个空的初始列表

于 2012-10-11T10:32:34.810 回答
2

使用动态编程，您可以将解决方案表示为

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

添加额外的备忘录也会加速这个程序

于 2012-10-11T10:56:23.300 回答
0

您可以迭代集合的长度。在每个步骤中，检查长度的所有子集k：

for k = 1 to size(input):
    foreach permutation p of length k:
        if sum(p) == 12:
            bam!
于 2012-10-11T10:28:28.030 回答