使用PHP函數來解決缺少的數字

Question

我有一個16位數字的池1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768。我有一個由16個數字的組合組成的數字，使用1到16個數字相加。例如，我有一個數字671，它由1 + 2 + 4 + 8 + 16 + 128 + 512組成。我試圖找出一種方法來取得我的16位數字和我的總數，並確定使用哪個數字來製作總數。我將使用PHP來做到這一點，我曾嘗試過搜索和數學離我強大的訴訟很遠，我試圖找到解決這個問題的空洞。

Answer 1

這是一個典型的Subset sum problem

你可以有一個簡單的回溯實現這一

echo "<pre>"; 
$ns = array(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768); 
print_r(subsetSum($ns, 671)); 

輸出

Array 
(
    [0] => 1 + 2 + 4 + 8 + 16 + 128 + 512 
) 

功能用於

function subsetSum($arr, $val, $i = 0) { 
    $r = array(); 
    while($i < count($arr)) { 
     $v = $arr[$i]; 
     if($v == $val) 
      $r[] = $v; 
     if($v < $val) 
      foreach(subsetSum($arr, $val - $v, $i + 1) as $s) 
      $r[] = "$v + $s"; 
     $i++; 
    } 
    return $r; 
}