Интересные интересности и задачи/головоломки

[Sibedir]

Сообщение от Poma][a

Вот. Прекрасная задачка:
Дается массив A, который содержит ровно N натуральных чисел, и число S. Нужно определить можно ли составить S из суммы элементов А.

Poma][a, ну это же не простой перебор? Сложность задачи при хучших начальных условиях меньше чем N! ?

[Poma][a]

Сложность задачи при хучших начальных условиях меньше чем N! ?

Ага. Меньше

[Sibedir]

Ну я пока нашел алгоритм со сложностью N*(N+1)/2 (треугольное число). Памяти он соответственно требует SizeOf(S) * (N*(N+1)/2).
Полагаю, это не то. Так как алгоритм в итоге дает еще и сам набор элементов, кроме ответа на поставленный вопрос: ДА/НЕТ.

[Poma][a]

Какое решение я хотел услышать - я пока не вспомнил
Пока вижу такие решения :
перебор 2^N
Сортировка с перебором. Сложность пока не понял какая.. Описываем функцию F(K, SUM) = F(K-1, SUM) OR F(K-1, SUM - A[K])
Можно рюкзаком за N*S

[MihalNik]

Дается массив A, который содержит ровно N натуральных чисел

Произвольных или первых подряд?
Если 1, то задача - сложная в смысле алгоритма.
Если 2, то простейшая.

[Poma][a]

Произвольных или первых подряд?

Произвольных

[Sibedir]

Да, Poma][a, я нагнал.
У меня сейчас как ты сказал. Только, если быть точным, перебор (2^N)-1. А эта прогрессия возрастает куда быстрее треугольной.

Poma][a, так а это... блин... у тя чё, нет более рационального решения?
i.jpg

[Аватар]

https://ru.wikipedia.org/wiki/%D0%97...81%D1%82%D0%B2

[Sibedir]

Да, всё так Аватар. Но поставленная задача (буквально) не в нахождении самого подмножества, а в определении того, существует оно или нет. Порой алгоритм ответа на вопрос "Есть решение или нет?" может сильно отличаться от самого решения. Я думал вся соль в этом.

[Аватар]

ИМХО почти 100% - в этой задаче найти одну из комбинаций и есть решение. Иначе нужно придумать новый писк в математике и очень существенный писк, почти крик. Повторяю - ИМХО