尋找一個數字的潛在組合（給定一個數字集可供選擇）

我一直在尋找一段時間來嘗試爲某個問題達成某種解決方案，這個問題目前正在阻礙我正在嘗試的任務去完成。我遇到過其他編程語言的一些解決方案，儘管我嘗試這麼做，但我實在無法理解。我還看到了很多關於這個問題的術語，例如排列，重構，子集總和，一美元硬幣等。尋找一個數字的潛在組合（給定一個數字集可供選擇）

如果我正在討論這個錯誤的方法，請隨時讓我知道。

這裏的果殼中的問題：給定一組（陣列）數字

，例如：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

尋找一個數字的潛在組合（給定一個數字集可供選擇）

回答

相關問題