Сумма из чисел массива, наиболее близкая к определенному числу с минимальным остатком
Подскажите правильный алгоритм, или решение на php.
Есть число
x = 112;
и массив
[20,30,38]
И число, и массив могут меняться.
Мне нужно получить число, максимально близкое к числу X, из суммы элементов массива, при условии, что числа из массива могут повторяться.
То есть из примера, который мне нужен
20+20+20+20+30 = 110 ( остаток 2)
или
30+30+30+20 = 110 ( остаток 2)
Заранее благодарю вас за совет.
Ответы (1 шт):
Автор решения: Stanislav Volodarskiy
→ Ссылка
Элемент $f[$i] содежит истину, если можно построить сумму $i из элементов массива $a. Заполняется слева направо. Сложность count($a) * $t:
<?php
$a = [20, 30, 38];
$t = 112;
$f = [];
for ($i = 0; $i <= $t; ++$i) {
$f[] = false;
}
$f[0] = true;
for ($i = 0; $i <= $t; ++$i) {
if ($f[$i]) {
foreach($a as $v) {
if ($i + $v <= $t) {
$f[$i + $v] = true;
}
}
}
}
for ($i = $t; $i >= 0; --$i) {
if ($f[$i]) {
echo $i;
echo "\n";
break;
}
}
?>