Задача: Как из ограниченного количества чисел найти те, из которых можно составить вводимое число?

Question

[AVoiNN]

Добрый день, дорогое сообщество!
Столкнулся со следующей алгоритмической задачей:
Дано число, например 2028
а так же дан список чисел, вводимых с клавиатуры: 1000, 56, 28, 88, 1999
Необходимо составить такой алгоритм, который выводил бы числа(пары, тройки...) из которых можно составить первое число(т.е. число 2028)

Можно реализовать на любом языке программирования либо на псевдокоде.
Буду очень благодарен за любую помощь!

Answer 1

[dmshar]

Полный перебор. С возможным окончанем иттерации при превышении текущей суммы заданного числа.

Comments

[xmoonlight]

Это НЕ полный перебор! Не обманывайте!

[Сергей Соколов]

dmshar всё правильно пишете, задача сводится к одномерной «упаковке рюкзака», которая NP-полная.

[xmoonlight]

Сергей Соколов, нет там перебора)))
Это задача на достижение нужного критерия.

[dmshar]

xmoonlight,
1. Приведите этот критерий.
2. Приведите НЕПЕРЕБАРНЫЙ алгоритм поиска в соответсвии с сформулированном критерием.
Ждем-с.

[xmoonlight]

dmshar, сразу после того, как приведёте алгоритм полного перебора.
Это не сарказм, а условие, избавляющее от "я об этом и говорил" (ложная аргументация).

[Сергей Соколов]

dmshar, не тратьте время на балабола.

[xmoonlight]

Сергей Соколов,

всё правильно пишете, задача сводится к одномерной «упаковке рюкзака», которая NP-полная.

стыдно должно быть тебе, как математику.

[dmshar]

Поскольку как эту задачу решить полным перебором понятно, все замерли в ожидании более быстрого алгоритма. Ну или хотя-бы "нужного критерия". Сразу хочу сказать, что предварительная сортировка массива в данной постановке выигрыша (сокращения количества просматриваемых вариантов) - не дает.