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