Набрать сумму чисел (Delphi)

[d3qoot]

Здравствуйте!
Не могу сообразить, как сделать следующее: необходимо набрать сумму из предоставленных чисел, не больше заданного числа.
К примеру дан массив: 2 7 5 3 7, из этих чисел нужно собрать число, к примеру 16. Т.е. 2+7+7 = 16. Подскажите, пожалуйста реализацию?

[Serge_Bliznykov]

только полный перебор..
для небольшого количества чисел (до 30) будет работать достаточно быстро и с гарантией получения наиболее оптимального решения.

а за конкретными алгоритмами и решениями очень рекомендую сходить в тему:
Выборка чисел

и сюда
подбор группы файлов до заданого размера

[d3qoot]

К сожалению, по условию задачи чисел может быть до 1000.
Накидал примерный алгоритм, не знаю, получится ли:
Как в задании, нам нужно найти сумму 16.

Ищем в массиве 16. Если 16 нет, ищем 15 и т.д. пока не встретится число, которое есть в массиве.
Нашли - это число 7. В переменную запишем, сколько нам ещё осталось искать в массиве, т.е. - 16-7=9 и обнулим использованную ячейку массива.
Дальше ищем по массиву 9, 8, 7. Встречается ещё раз 7.
Запишем в переменную 9-7=2 и обнулим использованную ячейку.
Далее ищем в массиве уже 2. Если находим - выход. Если не находим начинаем поиск заново, но не используя первое число 7.

Есть какие-нибудь мысли?

[Stilet]

только полный перебор..

А просто отсортировать и брать с самых минимальных пока не сравниться с нужным числом?

[d3qoot]

Сообщение от Stilet

А просто отсортировать и брать с самых минимальных пока не сравниться с нужным числом?

Так в том то и дело, что данная сумма (в задаче) набирается из двух наибольших (7) и одного самого маленького!

Пытался реализовать свой алгоритм, который написал в 3 сообщении, но что-то пока не получилось.

[Serge_Bliznykov]

Сообщение от d3qoot

набрать сумму из предоставленных чисел, не больше заданного числа.

d3qoot, поясните условие. Нужно набрать сумму ТОЧНО совпадающую с заданным числом, или "не более заданного числа" ?

Если сумму нужно набрать точную (а в случае, когда это нельзя сделать точно - выдавать сообщение о том, что это сделать). И перебор чисел из отсортированного массива не займёт много времени даже для 1000 чисел.

если же сумма может быть меньше заданного числа, тогда вопрос - это должна быть ОПТИМАЛЬНО ВОЗМОЖНАЯ сумма?
Если нет - то опять таки задача сильно упрощается.

Если не секрет, Вы это для чего делаете?

[d3qoot]

Serge_Bliznykov, Готовлюсь к олимпиаде.
Само по себе условие должно быть такое:

min<a<max

где:
A - число, которое нужно набрать из массива.

Для примера:
min = 25
max = 27
соответственно, необходимо набрать сумму из массива равной 26.