delphi. как построить логику

[Blazer]

есть N чисел и одно число M.
Так вот, как найти суму чисел из N, которая максимально близкая к числу M.

пример: есть числа 9 3 13 8 и число М=25,
то результатом будет 13+3+9=25, так как оно самое близкое к числу М.

 

[Пух]

1) отсортировать по возрастанию.
2) Брать число, которое максимально близко к M (но меньше M).
3) Найти разницу между M и найденным числом и запомнить найденное число
4) Повторить пункты 2 и 4, но искать максимум не с М, а с разницей. И не учитывать число, которое брали в пункте 2.
5) найти сумму чисел с п.3

 

[Hamster]

2,3,4,5,6,7,10
М=11.
По твоей логике первое число - уже 10.
А правильный ответ, например 5+6.

 

[Тарас]

генерируй массив всех возможных сумм массива Н, меньшую или равную числу М, а потом выбери максимальную. При генерации записывай числа сумм и саму сумму в какую то структуру. Ведь нету ограничений на время и память.

 

[Alexsandr]

You must be registered for see links

Естестенно предварительно отобрать в массив числа меньше искомого.

 

[Пух]

2,3,4,5,6,7,10
М=11.
По твоей логике первое число - уже 10.
А правильный ответ, например 5+6.

Да, согласен.

Можно по-другому сделать.
Начать проходить массив с конца. Найдем число 10. Потом поиском (бинарный поиск, сложность log2N) найти число, которое равно (приоритет) или хотя бы меньше чем M - 10 (11-10 = 1). Если найдено число, которое равно разнице - завершить работу и вывести запомненные числа на экран. Если найдено число меньше, чем разница (в нашем случае просто не удачный пример), то искать тем же поиском ещё число, которое равно(приоритет) или меньше чем новая разница.

Если не будет найдено такие числа, что сумма их равна M, значит нужно брать 2е число с конца массива (в примере 7) и никогда не брать числа, большие этого числа. Дальше проделать ту же операцию. В итоге, если не будет найдено множество чисел, сумма которых точно равна M, то вывести на экран все комбинации (если их несколько), которые максимально приближаются к M.
Так вроде будет работать правильно.

 

[Blazer]

спасибо всем, я решил уже)

 

[Пух]

как?

 

[Blazer]

1 - выстраиваю массив по возрастанию
2 - нахожу сумму всех чисел
3 - от этой суммы вычитываю сначала масива по 1му елементу начиная от меньшего до тех пор пока эта сумма станет меньше или равна числу заданному М
4 - каждое из чисел сумы выписуется, вошедшое по условию
5 - ети числа обнуляются с массива
6 - идет по циклу наново ищется сумма и вычитываются числа от мелкого
примерно такая логика

 

[Пух]

и что, оно работает правильно для такого набора?

2,3,4,5,6,7,10
М=11.

Получается
1)2,3,4,5,6,7,10
2)2+3+4+5+6+7+10 = 37
3)37-2-3-4-5-6-7 = 10
4) записываем 10, а решение 5 и 6.