PHP: Trouvez deux numéros ou plus d'une liste de nombres qui s'additionnent vers une quantité donnée

une solution probablement inefficace mais simple avec de la backtracking xxx

exemple xxx

résultat xxx

Si vous regardez Algorithme d'Oézis Un inconvénient est immédiatement effacé: il passe beaucoup de temps à résumer des chiffres qui sont déjà connus de ne pas travailler. (Par exemple, si 1 + 2 est déjà trop gros, il n'a aucun sens d'essayer 1 + 2 + 3, 1 + 2 + 3 + 3 + 4, 1 + 2 + 3 + 4 + 5, ..., aussi .)

Ainsi, j'ai écrit une version améliorée. Il n'utilise pas Bit Magic, il fait tout le manuel. Un inconvénient est que les valeurs d'entrée doivent être triées (utilisez lsort code>). Mais cela ne devrait pas être un gros problème;) p> xxx pré>

version modifiée du programme de test OEZIS (voir fin) sorties: p>

// Inputs
$n = array();
$n[0]  = 6.56;
$n[1]  = 8.99;
$n[2]  = 1.45;
$n[3]  = 4.83;
$n[4]  = 8.16;
$n[5]  = 2.53;
$n[6]  = 0.28;
$n[7]  = 9.37;
$n[8]  = 0.34;
$n[9]  = 5.82;
$n[10] = 8.24;
$n[11] = 4.35;
$n[12] = 9.67;
$n[13] = 1.69;
$n[14] = 5.64;
$n[15] = 0.27;
$n[16] = 2.73;
$n[17] = 1.63;
$n[18] = 4.07;
$n[19] = 9.04;
$n[20] = 6.32;

// Convert to Integers
foreach ($n as &$num) {
    $num *= 100;
}
$sum = 57.96 * 100;

// Sort from High to Low
rsort($n);

// Measure time
$start = microtime(true);
echo 'possibilities: ', count($result = array_sum_parts($n, $sum)), '<br />';
echo 'took: ', microtime(true) - $start;

// Check that the result is correct
foreach ($result as $element) {
    $s = 0;
    foreach ($element as $i) {
        $s += $n[$i];
    }
    if ($s != $sum) echo '<br />FAIL!';
}

var_dump($result);