php - 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

これは典型的な部分和問題です

これを達成するために簡単なバックトレースを行うことができます

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