如果你看看 oezis 算法 一个缺点很明显:它花费大量时间总结已知不起作用的数字.(例如，如果 1 + 2 已经太大，那么尝试 1 + 2 + 3、1 + 2 + 3 + 4、1 + 2 + 3 + 4 + 5、... 也没有任何意义.)

因此我写了一个改进的版本.它不使用一点魔法，它使一切都是手动的.一个缺点是，它需要对输入值进行排序(使用 rsort).但这应该不是什么大问题;)

function array_sum_parts($vals, $sum){
=数组()；$pos = array(0 => count($vals) - 1);$lastPosIndex = 0;$currentPos = $pos[0];$currentSum = 0;而(真){$currentSum += $vals[$currentPos];if ($currentSum 

；}

oezis 测试程序的修改版本(见末尾)输出:

可能性:540拍摄:3.0897309780121

所以执行只需要 3.1 秒，而 oezis 代码在我的机器上执行 65 秒(是的，我的机器很慢).这比 快 20 倍！

此外，您可能会注意到，我的代码发现了 540 而不是 338 的可能性.这是因为我调整了测试程序以使用整数而不是浮点数.直接浮点比较很少是正确的做法，这是一个很好的例子，为什么:你有时会得到 59.959999999999 而不是 59.96，因此比赛将不计算在内.所以，如果我用整数运行 oezis 代码，它也会找到 540 种可能性；)

测试程序:

//输入$n = 数组()；$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;//转换为整数foreach ($n as &$num) {$num *= 100;}$sum = 57.96 * 100;//从高到低排序rsort($n);//测量时间$start = microtime(true);echo '可能性:', count($result = array_sum_parts($n, $sum)), '<br/>';echo 'took: ', microtime(true) - $start;//检查结果是否正确foreach ($result as $element) {$s = 0;foreach ($element as $i) {$s += $n[$i];}if ($s != $sum) echo '<br/>FAIL!';}var_dump($result);

I am trying to create a little php script that can make my life a bit easier. Basically, I am going to have 21 text fields on a page where I am going to input 20 different numbers. In the last field I will enter a number let's call it the TOTAL AMOUNT. All I want the script to do is to point out which numbers from the 20 fields added up will come up to TOTAL AMOUNT.

Example:

field1 = 25.23
field2 = 34.45
field3 = 56.67
field4 = 63.54
field5 = 87.54
....
field20 = 4.2

Total Amount = 81.90

Output: field1 + fields3 = 81.90

Some of the fields might have 0 as value because sometimes I only need to enter 5-15 fields and the maximum will be 20.

If someone can help me out with the php code for this, will be greatly appreciated.

If you look at oezis algorithm one drawback is immediately clear: It spends very much time summing up numbers which are already known not to work. (For example if 1 + 2 is already too big, it doesn't make any sense to try 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ..., too.)

Thus I have written an improved version. It does not use bit magic, it makes everything manual. A drawback is, that it requires the input values to be sorted (use rsort). But that shouldn't be a big problem ;)

function array_sum_parts($vals, $sum){
    $solutions = array();
    $pos = array(0 => count($vals) - 1);
    $lastPosIndex = 0;
    $currentPos = $pos[0];
    $currentSum = 0;
    while (true) {
        $currentSum += $vals[$currentPos];

        if ($currentSum < $sum && $currentPos != 0) {
            $pos[++$lastPosIndex] = --$currentPos;
        } else {
            if ($currentSum == $sum) {
                $solutions[] = array_slice($pos, 0, $lastPosIndex + 1);
            }

            if ($lastPosIndex == 0) {
                break;
            }

            $currentSum -= $vals[$currentPos] + $vals[1 + $currentPos = --$pos[--$lastPosIndex]];
        }
    }

    return $solutions;
}

A modified version of oezis testing program (see end) outputs:

possibilities: 540
took: 3.0897309780121

So it took only 3.1 seconds to execute, whereas oezis code executed 65 seconds on my machine (yes, my machine is very slow). That's more than 20 times faster!

Furthermore you may notice, that my code found 540 instead of 338 possibilities. This is because I adjusted the testing program to use integers instead of floats. Direct floating point comparison is rarely the right thing to do, this is a great example why: You sometimes get 59.959999999999 instead of 59.96 and thus the match will not be counted. So, if I run oezis code with integers it finds 540 possibilities, too ;)

Testing program:

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