Algorithm to find nearest values for total sum in PHP

Question

I have a total_sum variable (for example 20.00) and array which is not exactly equal the combination of this total_sum but very close: array = [array(8=>1.49), array(1=>8.1)] (array could have more values) index is a multiplier key value: (8*1.49 + 1*8.1) = 20.02 != total_sum. I need to find algorithm who improves array values to be equal to total_sum. Key of array can't be changed, only values. Values need have only two decimal places (prices/money)

So result of this example array will be: array(8*1.49 + 1*8.8) [8.1 changed to 8.8 so total_sum now = 20.00]

Do somebody know such problem or maybe this problem has a name?

Answer 1

So i had a little fun with this for the past hour :D. Here is the result. Hope it is what you're expecting. From the comments I understood that you want to have only double precision value. This function will loop through until it matches double precision value. Notice: there may be better ways of doing it, but this is the first that came to my mind.

function correction( $total, $input = array(), &$correction = null, $index = 0 ){
    if( count( $input ) < $index ){
        return;
    }
    $total_sum = 0;
    foreach( $input as $multiplier => $value ){
        $total_sum += $multiplier * $value;
    }
    $remains = 0;
    $i = 0;
    foreach( $input as $multiplier => $value ){
        if( $i !== $index ){
            $remains += $multiplier * $value;
        }
        $i++;
    }
    $rest = $total - $remains;
    reset( $input );
    $current_key = 0;
    for( $i = 0; $i < $index; $i++ ){
        next( $input );
    }
    $current_key = key( $input );
    if( $current_key !== null ){
        $value = $rest / $current_key;
        $precision = strlen( $value ) - strpos( $value, '.' ) - 1;
        if( $precision > 2 ){
            $index++;
            correction( $total, $input, $correction, $index );
        } else {
            $correction = array(
                'index' => $current_key,
                'value' => $value,
            );
        }
    }
}

Some sample data:

$total = 20;
$input = array(
    8 => 1.49,
    1 => 8.1,
);
correction( $total, $input, $correction );
echo '<pre>'; print_r( $correction ); echo '</pre>';

Result:

Array
(
    [index] => 1
    [value] => 8.08
)

Another sample:

$total = 20;
$input = array(
    8 => 1.49,
    1 => 8.1,
    3 => 2.1,
);

Result:

Array
(
    [index] => 1
    [value] => 1.78
)

LE:

public static function correction( $total, $input = array(), &$correction = null, $index = 0 ){
    if( count( $input ) < $index ){
        return;
    }
    $total_sum = 0;
    foreach( $input as $data ){
        // if input is coming from user then
        // you may want to check if indexes are set
        $total_sum += $data['multiplier'] * $data['value'];
    }
    $remains = 0;
    $i = 0;
    foreach( $input as $data ){
        if( $i !== $index ){
            // same check here
            $remains += $data['multiplier'] * $data['value'];
        }
        $i++;
    }
    $rest = $total - $remains;
    $value = isset( $input[ $index ]['multiplier'] ) && $input[ $index ]['multiplier'] > 0 ?
                $rest / $input[ $index ]['multiplier'] : 0;
    $precision = strlen( $value ) - strpos( $value, '.' ) - 1;
    if( $precision > 2 ){
        $index++;
        self::correction( $total, $input, $correction, $index );
    } else {
        $correction = array(
            'index' => $index,
            'value' => $value,
        );
    }
}
$total = 68;
$input = array(
    array(
        'multiplier' => 1,
        'value'      => 1.2,
    ),
    array(
        'multiplier' => 8,
        'value'      => 5,
    ),
);