PHP:从一个给定数量的数字列表中找到两个或多个数字 [英] PHP: find two or more numbers from a list of numbers that add up towards a given amount

问题描述

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

例子:

field1 = 25.23字段2 = 34.45字段3 = 56.67字段4 = 63.54字段5 = 87.54……字段 20 = 4.2总金额 = 81.90

输出:field1 + fields3 = 81.90

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

如果有人可以帮助我解决此问题的 php 代码，将不胜感激.

解决方案

如果你看看 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 <$sum && $currentPos != 0) {$pos[++$lastPosIndex] = --$currentPos;} 别的 {if ($currentSum == $sum) {$solutions[] = array_slice($pos, 0, $lastPosIndex + 1);}如果($lastPosIndex == 0){休息;}$currentSum -= $vals[$currentPos] + $vals[1 + $currentPos = --$pos[--$lastPosIndex]];}}返回
解决方案
；}

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

这篇关于PHP:从一个给定数量的数字列表中找到两个或多个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！