Optimizing Find nearest sum of numbers in array to a given number

Question

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:

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

Then the method should return 5000 and 1000

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

I've tried with code below, here is working one but if the $desiredSum and $numbers array is big. it's running so slow until php execution timeout

$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";

Anyone can help me out ?

Answer 1

<?php

function coinChange($numbers,$desiredSum){
    sort($numbers);
    $set = [];
    $set[0] = [];

    for($i = $numbers[0];$i <= $desiredSum;++$i){
        foreach($numbers as $index => $current_number){
            if($i >= $current_number && isset($set[$i - $current_number])){
                if(isset($set[$i - $current_number][$index])) continue;
                $set[$i] = $set[$i - $current_number];
                $set[$i][$index] = true;
                break;
            }
        }
    }

    if(count($set) === 0){
        return [0,[]];
    }

    if(isset($set[$desiredSum])){

        return [
            $desiredSum,
            formatResult($numbers,array_keys($set[$desiredSum]))
        ];
    }else{
        $keys = array_keys($set);
        $nearestSum = end($keys);
        $sum = 0;
        $rev_numbers = array_reverse($numbers);
        $result = [];
        foreach($rev_numbers as $number){
            $sum += $number;
            $result[] = $number;
            if($sum > $nearestSum && abs($nearestSum - $desiredSum) > abs($sum - $desiredSum)){
                $nearestSum = $sum;
                break;
            }else if($sum > $nearestSum && abs($nearestSum - $desiredSum) < abs($sum - $desiredSum)){
                $result = formatResult($numbers,array_keys($set[$nearestSum]));
                break;
            }
        }

        return [
            $nearestSum,
            $result
        ];
    }
}

function formatResult($numbers,$keys){
    $result = [];
    foreach($keys as $key) $result[] = $numbers[$key];
    return $result;
}

print_r(coinChange([10000,5000,1000,1000],14000));
print_r(coinChange([10000,5000,1000,1000],13000));
print_r(coinChange([100000,100000,100000,100000,100000,100000,50000,50000,50000,50000,10000,10000,500,500,500,1000,1000],250000));
print_r(coinChange([100000,100000,100000,100000,100000,100000,50000,50000,50000,50000,10000,10000,500,500,500,1000,1000],179999));

Demo: https://3v4l.org/hBGeW

Algorithm:

• This is similar to coin change problem.

• We first sort the numbers.

• Now, we iterate from minimum number in the array to the desired sum.
• Inside it, we iterate through all elements in the array.
• Now, we can make $i(which is a sum) only if we have made sum $i - $current_number. If we have the previous one, then we add $current_number to our collection for sum $i.

Two Scenarios:

• If we can make the exact sum, then we return the result as is.
• If we can't, then are 2 possibilities:
  • We would already have nearest sum possible in our $set which would be the last entry. We keep them in a variable.
  • Now, the nearest sum could also be higher than the desired sum. So, we get the larger sum and check if it's nearer than nearest smallest sum and then compare both and return the result.

Result format:

Let's take the below sample output:

Array
(
    [0] => 15000
    [1] => Array
        (
            [0] => 10000
            [1] => 5000
        )

)

It simply means that the first index is the nearest sum possible and array at 2nd index is all elements it took from $numbers to make that sum.