查找数组中与给定数字最接近的数字总和 [英] Find nearest sum of numbers in array to a given number

问题描述

说我有一个数组[10000,5000,1000,1000] ，我想找到最接近给定数字的数字总和。抱歉，我们的解释不正确，但是有一个例子：

Say I have an array [10000,5000,1000,1000] and I would like to find the closest sum of numbers to a given number. Sorry for the bad explanation but here's an example:

说我有一个数组[10000,5000,1000,1000] 我想找到最接近的数字，例如 6000 。

Say I have an array [10000,5000,1000,1000] I want to find the closest numbers to, say 6000.

然后该方法应返回 5000和1000

另一个例子：我们想要最接近 14000 的东西，因此他应该返回 10000和5000

another example : we want the closest to 14000 , so then he should return 10000 and 5000

在这里我尝试过php，但是当我输入 6000 时出现了问题，我应该得到 5000和1000

here i've tried on php but it's something wrong when i put 6000 i should get 5000 and 1000

<?php

$arr    = [10000,5000,1000,1000];
$x      = 6000;
var_dump(eek($x,$arr));

function eek($x,$arr)
{
    $index = [];
    $counter = 0;
    foreach($arr as $val)
    {
        if($counter + $val <= $x)
        {
            $counter += $val;
            $index[] = $val;
        }
        elseif($counter + $val >= $x)
        {
            $counter += $val;
            $index[] = $val;
            break;
        }
    }

    if($counter == $x)
    {
        return $index;
    }
    elseif($counter >= $x)
    {
        return $index;    
    }
    else
    {
        return [];
    }
}

?>

有人对此有解决方案吗？

Anyone have solution about it ?

推荐答案

此处适用于float和负值：

Here it is works with float and negative values:

$numbers = array(
    10000,5000,1000,1000
);
$desiredSum = 6000;
$minDist = null;
$minDist_I = null;
// Iterate on every possible combination
$maxI = pow(2,sizeof($numbers));
for($i=0;$i<$maxI;$i++) {
    if(!(($i+1) % 1000)) echo ".";

    // Figure out which numbers to select in this 
    $sum = 0;
    for($j=0;$j<sizeof($numbers);$j++) {
        if($i & (1 << $j)) {
            $sum += $numbers[$j];
        }
    }
    $diff = abs($sum - $desiredSum);
    if($minDist_I === null || $diff < $minDist) {
        $minDist_I = $i;
        $minDist = $diff;
    }

    if($diff == 0) break;
}
$chosen = array();
for($j=0;$j<sizeof($numbers);$j++) {
    if($minDist_I & (1 << $j)) $chosen[] = $numbers[$j];
}
echo "\nThese numbers sum to " . array_sum($chosen)  . " (closest to $desiredSum): ";
echo implode(", ", $chosen);
echo "\n";

这篇关于查找数组中与给定数字最接近的数字总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！