php - 使用 PHP 函数解决丢失的数字

Question

我有 16 个号码池 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768。我有一个数字，它由 16 个数字的某种组合组成，其中 1-16 个数字相加。例如，我有一个由 1+2+4+8+16+128+512 组成的数字 671。我试图找出一种方法来获取我的 16 个数字池和我的总数，并确定哪些数字用于构成该总数。我将使用 php 来执行此操作，但我曾经尝试过搜索，而数学远非我的强项，我试图找到解决此问题的方法却一无所获。

Answer 1

这是一个典型的子集和问题

你可以有一个简单的回溯来实现这一点

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