寻找一个数字的潜在组合（给定一个数字集可供选择）

我一直在寻找一段时间来尝试为某个问题达成某种解决方案，这个问题目前正在阻碍我正在尝试的任务去完成。我遇到过其他编程语言的一些解决方案，尽管我尝试这么做，但我实在无法理解。我还看到了很多关于这个问题的术语，例如排列，重构，子集总和，一美元硬币等。寻找一个数字的潜在组合（给定一个数字集可供选择）

如果我正在讨论这个错误的方法，请随时让我知道。

这里的果壳中的问题：给定一组（阵列）数字

，例如：2, 3, 7, 14，我怎么能找到的那些数字的组合加起来（或等于）特定总和，例如：14。

对于上面的例子中号的一些可能的组合的一个例子：

3 + 3 + 3 + 3 + 2 
7 + 3 + 2 + 2 
7 + 7 
14

因为我试图解决的问题是在PHP，我想如果有一个解决方案爱可以用这种语言提供。如果不是的话，即使有人能更好地解释我想解决的问题，以及这样做的潜在方法，我会非常感激。或者如果我可能会以这种错误的方式进行讨论，那么我全都是耳朵。

来源

2015-02-11 Jay Are

通过动态规划思考 – sashas 2015-02-11 11:51:21

您是在寻找实际的组合，或者只是其中有多少？可能有指数级的组合，所以如果你真的需要所有的组合，它会快速增长（但是找到它们的数量对于较小的整数更容易） – amit 2015-02-11 12:33:25

我需要实际的组合。数字集是预定义集的一部分（不是动态的），它们几乎被设置为[3,4,5,6,7,14]，并且变量和的范围将处于1 -30。我想基于这些值的结果集不应该太过失控。 – 2015-02-11 12:41:36

要生成所有解决方案，您需要使用某种回溯，如果第一个数字在解决方案中，则“猜测”，并为每个可能性递归（需要对结果进行求和，或者它不是）。

类似下面的伪代码：

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

来源

2015-02-11 12:51:17 amit

我并不完全清楚addLast和removeLast方法会做什么 – 2015-02-11 13:01:25

@JayAre currentResult是某种动态数组（在C++中为向量，Java中为ArrayList）或链表 - 以及addLast（e）将元素“e”添加到列表末尾（附加它），'removeLast（）'只是从同一列表中删除最后一个元素（有效地将其大小减1）。 – amit 2015-02-11 13:03:31

这就是我设法拿出迄今为止，基于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);

来源

2015-02-11 15:52:13

寻找一个数字的潜在组合（给定一个数字集可供选择）

回答

相关问题