|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
16.08.2015, 20:15 | #1401 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
|
17.08.2015, 00:09 | #1402 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
18.08.2015, 14:09 | #1403 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Ну я пока нашел алгоритм со сложностью N*(N+1)/2 (треугольное число). Памяти он соответственно требует SizeOf(S) * (N*(N+1)/2).
Полагаю, это не то. Так как алгоритм в итоге дает еще и сам набор элементов, кроме ответа на поставленный вопрос: ДА/НЕТ. |
18.08.2015, 22:22 | #1404 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Какое решение я хотел услышать - я пока не вспомнил
Пока вижу такие решения : перебор 2^N Сортировка с перебором. Сложность пока не понял какая.. Описываем функцию F(K, SUM) = F(K-1, SUM) OR F(K-1, SUM - A[K]) Можно рюкзаком за N*S Последний раз редактировалось Poma][a; 18.08.2015 в 22:30. |
18.08.2015, 22:38 | #1405 | |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,657
|
Цитата:
Если 1, то задача - сложная в смысле алгоритма. Если 2, то простейшая.
Благими намерениями устлана дорога на programmersforum.ru
Последний раз редактировалось MihalNik; 19.08.2015 в 01:57. |
|
18.08.2015, 22:47 | #1406 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
19.08.2015, 06:48 | #1407 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Да, Poma][a, я нагнал.
У меня сейчас как ты сказал. Только, если быть точным, перебор (2^N)-1. А эта прогрессия возрастает куда быстрее треугольной. Poma][a, так а это... блин... у тя чё, нет более рационального решения? i.jpg Последний раз редактировалось Sibedir; 19.08.2015 в 06:57. |
19.08.2015, 07:42 | #1408 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
19.08.2015, 09:59 | #1409 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Да, всё так Аватар. Но поставленная задача (буквально) не в нахождении самого подмножества, а в определении того, существует оно или нет. Порой алгоритм ответа на вопрос "Есть решение или нет?" может сильно отличаться от самого решения. Я думал вся соль в этом.
|
19.08.2015, 10:37 | #1410 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
ИМХО почти 100% - в этой задаче найти одну из комбинаций и есть решение. Иначе нужно придумать новый писк в математике и очень существенный писк, почти крик. Повторяю - ИМХО
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
интересные проги | kipish | Софт | 85 | 18.12.2022 01:03 |
Текст на картинках | SunLight | Microsoft Office Word | 2 | 08.08.2007 12:59 |