массивы — алгоритм поиска ближайших значений для общей суммы в переполнении стека

Question

массивы — алгоритм поиска ближайших значений для общей суммы в переполнении стека

у меня есть total_sum переменная (например, 20.00) и массив, который не совсем равен комбинации этого total_sum но очень близко
array = [array(8=>1.49), array(1=>8.1)] (массив может иметь больше значений)
index — это значение ключа множителя: (8*1.49 + 1*8.1) = 20.02 != total_sum,
Мне нужно найти алгоритм, который улучшает значения массива, чтобы быть равным total_sum,
Ключ массива не может быть изменен, только значения. Значения должны иметь только два знака после запятой (цены / деньги)

Таким образом, результат этого примера массива будет: array(8*1.49 + 1*8.8) [8.1 изменено на 8.8, так total_sum сейчас = 20.00]

Кто-нибудь знает такую проблему или, может быть, у этой проблемы есть имя?

0

algorithm arrays php subtotal

Решение

Другие решения

Это не специфическая проблема php. Если вы используете поплавки, самое простое решение меняется всегда первое значение вашего массива, используя следующую формулу:

first_value = (total_sum - sum_of_all_other_values_and_multipliers) / multiplier_key

Если вы используете целые числа или ограниченную точность, у вас есть пример проблемы с рюкзаком: https://en.wikipedia.org/wiki/Knapsack_problem

1

Источник

Accepted Answer

Так что я немного повеселился за прошедший час: D. Вот результат. Надеюсь, это то, что вы ожидаете. Из комментариев я понял, что вы хотите иметь только значение двойной точности. Эта функция будет проходить до тех пор, пока не достигнет значения двойной точности. Обратите внимание: возможно, есть лучшие способы сделать это, но это первое, что пришло мне в голову.

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

Некоторые примеры данных:

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

Результат:

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

Другой образец:

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

Результат:

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

2