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?

If your problem are limited to floating points only (decimal places), you can try to use `floor` and `ceil` functions. That will find the integer above and below the value you computed and you'll be able to match it closely. — Marco Aurélio Deleu, Nov 13 '15 at 15:17
is it not an option to create the total_sum variable from the sum of the array values, then they will be equal? — Dale, Nov 13 '15 at 15:18
@Axalix: no, in your example result will be: array(1=>3), so there is always a solution — r_a_f, Nov 13 '15 at 15:24
http://stackoverflow.com/questions/2860432/common-strategies-to-deal-with-rounding-errors-in-currency-intensive-soft — Axalix, Nov 13 '15 at 15:32

Mujnoi Gyula Tamas · Accepted Answer · 2015-11-13T20:19:40.073

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,
    ),
);

I edited the function because I saw a minor error. I was returning the loop $i instead of the correct array index. So the way you would replace the value is pretty simple `$input[ $correction['index'] ] = $correction['value']` — Mujnoi Gyula Tamas, Nov 13 '15 at 17:21
also check if `$correction` is not null because if it's null than you don't have a possible 2 decimal precision replacement. — Mujnoi Gyula Tamas, Nov 13 '15 at 17:22
I also moved the `$current_key = key( $input );` outside of the loop because I only need to set it once also you can replace the second key call with `$current_key` variable,so it will be like `$value = $first / $current_key;` — Mujnoi Gyula Tamas, Nov 13 '15 at 17:24
agrr somebody minus this question and now I can't add score for your help because small amount score on my profile :/ — r_a_f, Nov 13 '15 at 17:25
Don't worry about it, I'm just glad I could help out. I updated the function again :P, I missed 2 things if current key is null and the precision needed to be exaclty 2 decimal for a valid correction, now the precision is working for integers, 1 point precision and 2 point precision decimal. ie. 1, 1.2, 1.23. You could further improve the function to calculate higher precision values if it couldn't find any 2 precision value and than reduce the precision to a near aproximation. 1.2345 => 1.23, while loosing the total sum precision. — Mujnoi Gyula Tamas, Nov 13 '15 at 19:43
You solve very interesting problem I think. But I also edit your function (old version) to work with array with not double index if you need to have same (multiplier) key: http://pastebin.com/PnL8BtWE coud you check it? `input = array(array(2=>1.22), array(5=>2.35))` et — r_a_f, Nov 13 '15 at 19:49
Well it's up to you how you modify it for your needs. :) To work with multiple key, one is to add it to a multidimensional array like the output. Best of luck :) Glad I could help you out. — Mujnoi Gyula Tamas, Nov 13 '15 at 19:56
OK, I added another edit to my answer, which should work perfectly, also added indexes to array so you can identify easier each sub array. Hope it works well. Usage is almost the same `$input[ $correction['index'] ]['value'] = $correction['value']` — Mujnoi Gyula Tamas, Nov 13 '15 at 20:22

svrnm · Answer 2 · 2015-11-13T15:58:05.640

1

This is not a php specific problem. If you use floats the easiest solution is changing always the first value of your array, using the following formular:

first_value = (total_sum - sum_of_all_other_values_and_multipliers) / multiplier_key

If you use integers or a limited precision, you have an instance of the knappsack problem: https://en.wikipedia.org/wiki/Knapsack_problem

edited Nov 13 '15 at 15:58

answered Nov 13 '15 at 15:21

svrnm

1,036
6
17

Yes, it work generally, but I not precise my problem.. I need to work with only two decimal places float numbers (prices). But your answer is right on normal float numbers. – r_a_f Nov 13 '15 at 15:40
1

in this case, you have the following problem: https://en.wikipedia.org/wiki/Knapsack_problem – svrnm Nov 13 '15 at 15:42
1

@axalix: array = [array(2 => 1.5)] ? - we are not talkinb about *exact*. If we are talking about integers, you have a knapsack problem. – svrnm Nov 13 '15 at 15:44
@Axalix: first_value = (3 - 0) / 2 = 3 = total_sum :) – r_a_f Nov 13 '15 at 15:45
k, another one :) `array = [array(7 => 2)]` and `total_sum = 0.37` then 2 should be replaced with 0.052857143. You said: _I need to work with only two decimal places float_ , so then you will use 0.05 x 7 = 0.35 – Axalix Nov 13 '15 at 15:56
@Axalix, yes but first time I not precise this problem so svrnm made this mathematical equation for all numbers. My bad to not precise this. – r_a_f Nov 13 '15 at 16:07

Algorithm to find nearest values for total sum in PHP

2 Answers2