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.
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.
示例:
field1 = 25.23
field2 = 34.45
field3 = 56.67
field4 = 63.54
field5 = 87.54
....
field20 = 4.2
Total Amount = 81.90
输出:字段1 +字段3 = 81.90
Output: field1 + fields3 = 81.90
某些字段的值可能为0，因为有时我只需要输入5-15个字段，最大值为20.
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.
如果有人可以通过此php代码帮助我，将不胜感激.
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.)
因此，我写了一个改进的版本.它不使用位魔术，而是使所有操作变为手动.缺点是，它要求对输入值进行排序(使用rsort).但这不应该是一个大问题；)
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;
}
oezis测试程序的修改版(请参阅末尾)输出:
A modified version of oezis testing program (see end) outputs:
possibilities: 540
took: 3.0897309780121
因此执行仅花费了 3.1秒，而oezis代码在我的计算机上执行了 65秒(是的，我的计算机非常慢).速度快了 20倍！
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!
此外，您可能会注意到，我的代码找到了540而不是338的可能性.这是因为我将测试程序调整为使用整数而不是浮点数. 直接进行浮点比较很少是正确的事，这是一个很好的例子，原因:您有时会得到59.959999999999而不是59.96，因此不计算匹配数.因此，如果我使用整数运行oezis代码，它也会发现540种可能性；)
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 ;)
测试程序:
// 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屋！
