Calculate from an array the number that is equal or higher and closest to a given number

Question

I need to calculate from a given array the number that is equal or higher and closest to a given number in PHP. Example:

Number to fetch:

6.85505196

Array to calculate:

3.11350000
4.38350000
4.04610000
3.99410000
2.86135817
0.50000000

Only correct combination should be:

3.99410000 + 2.86135817 = 6.85545817

Can somebody help me? It's been 3 hours I'm getting mad!

UPDATE: I finally finished my code as following:

$arr = array(3.1135, 4.3835, 4.0461, 3.9941, 2.86135817, 0.5);
$fetch = 6.85505196;
$bestsum = get_fee($arr, $fetch);
print($bestsum);

function get_fee($arr, $fetch) {
    $bestsum = 999999999;
    $combo = array();
    $result = array();
    for ($i = 0; $i<count($arr); $i++) {
        combinations($arr, $i+1, $combo);
    }
    foreach ($combo as $idx => $arr) {
        $sum = 0;
        foreach ($arr as $value) {
            $result[$idx] += $value;
        }
        if ($result[$idx] >= $fetch && $result[$idx] < $bestsum) $bestsum = $result[$idx];
    }
    return $bestsum;
}

function combinations($arr, $level, &$combo, $curr = array()) {
    for($j = 0; $j < count($arr); $j++) {
        $new = array_merge($curr, array($arr[$j]));
        if($level == 1) {
            sort($new);
            if (!in_array($new, $combo)) {
                $combo[] = $new;          
            }
        } else {
            combinations($arr, $level - 1, $combo, $new);
        }
    }
}

Answer 1

New updated code.

<?php
$x = 6.85505196;
$num = array(3.1135, 4.3835, 4.0461, 3.9941, 2.86135817, 0.5);
asort($num); //sort the array
$low = $num[0]; // lowest value in the array
$maxpossible = $x+$low; // this is the maximum possible answer, as we require the number that is equal or higher and closest to a given number 
$num = array_values($num);
$iterations = $x/$num[0]; // possible combinations loop, to equate to the sum of the given number using the lowest number
$sum=$num;
$newsum = $sum;
$k=count($num);
for($j=0; $j<=$iterations; $j++){   
    $l = count($sum);
    for($i=0; $i<$l; $i++){
        $genSum = $sum[$j]+$sum[$i];
        if($genSum <= $maxpossible){
            $newsum[$k] = $genSum;
            $k++;
        }
    }

    $newsum = array_unique($newsum);
    $newsum = array_values($newsum);
    $k = count($newsum);
    $sum = $newsum;
}
asort($newsum);
$newsum = array_values($newsum);
for($i=0; $i<count($newsum); $i++){
    if($x<=$newsum[$i]){
        echo "\nMaximum Possible Number = ".$newsum[$i];
        break;
    } 
}

?>

Answer 2

Thank you all for your help! My code is working pretty cool when is needed to fetch one or two numbers (addition) only. But can't figure out how to add more combinations up to the total count of elements in my given array. I mean if there are, let's say, 8 numbers in my array I want to try all possible combinations (additions to each other) as well. My actual code is:

    $bestsum = 1000000;
    for ($i = 0; $i < count($txinfo["vout"]); $i++) {
        if ($txinfo["vout"][$i]["value"] >= $spent && $txinfo["vout"][$i]["value"] < $bestsum) {
            $bestsum = $txinfo["vout"][$i]["value"];
        }
    }
    for($i = 0; $i < count($txinfo["vout"]); $i++) {
        $j = $i + 1;
        for($j; $j < count($txinfo["vout"]); $j++) {
            $sum = $txinfo["vout"][$i]["value"] + $txinfo["vout"][$j]["value"];
            if($sum >= $spent && $sum < $bestsum) {
                $bestsum = $sum;
            }
        }
    }
    $fee = bcsub($bestsum, $spent, 8);
    print("Fee: ".$fee);

Answer 3

I hope the following example might help you. Please try this

<?php
    $array = array(
            "3.11350000",
            "4.38350000",
            "4.04610000",
            "3.99410000",
            "2.86135817",
            "0.50000000"
            );

echo "<pre>";
print_r($array);// it will print your array

for($i=0; $i<count($array); $i++)
{
    $j=$i+1;

    for($j;$j<count($array); $j++)
        {
            $sum = $array[$i] + $array[$j];
            // echo $array[$i]. " + ".$array[$j]." = ".$sum."<br>"; //this will display all the combination of sum

            if($sum >= 6.85505196 && ($sum <= round(6.85505196)) )//change the condition according to your requirement
             {
              echo "The correct combinations are:<br/><br/>";
              echo "<b>". $array[$i]. " + ".$array[$j]." = ".$sum."<b>";
              echo "<br/>";
             }

        }
        echo "<br/>";

        }

    ?>

We will get the result as below

Array
 (
  [0] => 3.11350000
  [1] => 4.38350000
  [2] => 4.04610000
  [3] => 3.99410000
  [4] => 2.86135817
  [5] => 0.50000000
 )

The correct combinations are:

4.04610000 + 2.86135817 = 6.90745817

3.99410000 + 2.86135817 = 6.85545817

Answer 4

You should do it in two steps:

a. Work out (or look up) an algorithm to do the job.

b. Implement it.

You don't say what you've managed in the three hours you worked on this, so here's a "brute force" (read: dumb) algorithm that will do the job:

1. Use a variable that will keep your best sum so far. It can start out as zero:

   $bestsum = 0;
   

2. Try all single numbers, then all sums of two numbers, then all sums of three numbers, etc.: Every time you find a number that meets your criteria and is better than the current $bestsum, set $bestsum to it. Also set a second variable, $summands, to an array of the numbers you used to get this result. (Otherwise you won't know how you got the solution). Whenever you find an even better solution, update both variables.

3. When you've tried every number combination, your two variables contain the best solution. Print them out.

That's all. It's guaranteed to work correctly, since it tries all possibilities. There are all sorts of details to fill in, but you can get to work and ask here for help with specific tasks if you get stuck.