Надо запрограммировать сложение чисел

[evshi]

Есть число1=876, число2=277, число3=140 и Искомое число=1620 (ИЧ). Надо из предложенных чисел при помощи суммирования получить ИЧ таким образом, чтобы полученная сумма была наиболее близка к ИЧ.

Например, 876+277+277+140=1570 или 876+140+140+277+140=1573. Второй вариант лучше, т.к. 1573 ближе к 1620, чем 1570.

Надо как-то запрограммировать подобную задачу. Т.е. на вход поступает несколько чисел (их может быть сколько угодно), задаётся ИЧ и программа должна выдать вариант слагаемых, которые бы в сумме давали наиболее близкую сумму к ИЧ.

В какую сторону думать?

 

[fixxxer]

Выглядит как вариация на тему Unbounded knapsack problem. Хотя тут попроще вроде.

Если чисел немного - тупо полным перебором вариантов.

А откуда такие задачки?

 

[AnrDaemon]

Если чисел немного, перебором. Если много - строй мутатрон, проще будет.

 

[Vano]

Но не больше чем ИЧ?

 

[Vano]

Но не больше чем ИЧ?

Если да то вот :

$i = 1620;

$array = [277, 876, 140];

$sum = array_sum($array);

$diff = $i - $sum;
$reminders = [];

foreach ($array as $k => $v) {
    if ($v < $diff) {
        $reminders[$k] = $diff % $v;
    }
    if ($v == $diff) {
        echo 'stop lototron ->' . $v;
    }
}

asort($reminders);
reset($reminders);

echo($array[key($reminders)]);

 

[Adelf]

@Vano, ты задачу не понял.

 

[Vano]

@Vano, ты задачу не понял.

Ты абрикос

 

[antson]

@evshi, https://ru.wikipedia.org/wiki/Задача_о_ранце
Поддерживаю Фиксера . Стандартная задача из комбинаторики (рюкзак или ранец)
Полный перебор не спортивно. Из точных остается ветвей и границ.