PHP:从添加到给定数量的数字列表中找到两个或更多数字

Question

我正在尝试创建一个可以让我的生活更轻松的小PHP脚本.基本上,我将在一个页面上有21个文本字段,我将输入20个不同的数字.在最后一个字段中,我将输入一个数字,我们称之为TOTAL AMOUNT.我想让脚本做的就是指出添加的20个字段中的哪些数字将达到TOTAL AMOUNT.

例:

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

Total Amount = 81.90

输出:field1 + fields3 = 81.90

某些字段的值可能为0,因为有时我只需输入5-15个字段,最大值为20.

如果有人可以帮我解决这个问题的PHP代码,将不胜感激.

Answer 1

如果你看oezis算法,一个缺点是立即明确:它花费了很多时间来总结已知无法工作的数字.(例如,如果1 + 2已经太大,尝试1 + 2 + 3,1 + 2 + 3 + 4,1 + 2 + 3 + 4 + 5,......也没有任何意义.)

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

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

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

possibilities: 540
took: 3.0897309780121

因此,执行只需3.1秒,而oezis代码在我的机器上执行了65秒(是的,我的机器非常慢).这快了20多倍!

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

测试程序:

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