PHP 함수를 사용하여 누락 된 숫자를 해결합니다.

Question

나는 숫자가 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768 인 16 개의 풀을 가지고 있습니다. 나는 그들 중 1 - 16을 사용하는 16 개의 숫자의 조합으로 구성된 숫자를 더했습니다. 예를 들어 1 + 2 + 4 + 8 + 16 + 128 + 512에 의해 만들어진 숫자 671이 있습니다. 나는 16 개의 숫자와 총 숫자를 가진 풀을 가져 와서 총 숫자를 만드는 데 사용 된 숫자를 확인하는 방법을 찾으려고 노력 중이다. 나는 PHP를 사용하여 검색을 시도한 방법과 수학을 멀리하는 방법을 사용하여이 문제에 대한 해결책을 찾으려 고 노력하고 있습니다.

Answer 1

이다 전형적인 Subset sum problem

당신이 기능을 사용

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

이

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)); 

출력을 달성하기 위해 간단한 다시 추적을 할 수 있습니다

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; 
}