|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.11.2016, 15:23 | #1 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
задача о рюкзаке 0-1
Подскажите, пожалуйста, эксперты! Действительно ли, решение задачи о рюкзаке 0-1 можно рассматривать, как задачу нахождения быстрого (полиномиального) алгоритма для решения переборных задач? И за это деньги сулят? Или такие задачи не решаются для больших чисел? (допустим 12 тыс предметов и вес рюкзака 10 млрд)
помогать студентам - моя вторая профессия
|
20.11.2016, 15:34 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Благими намерениями устлана дорога на programmersforum.ru
|
20.11.2016, 16:02 | #3 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
Не верите? Проверьте...<ссылка удалена>
Уважаемый, заслуженный модератор! После Вашей ссылки на Википедию народ шарахается от темы как от "вечного двигателя"... Хоть бы один человек подтвердил, что "да... программа работает... и на тех данных, которые Википедия не считает реальными для решения". Наверное, это Вам придется сделать... Чтобы не жалеть потом об упущенной возможности протянуть руку помощи нуждающемуся...
помогать студентам - моя вторая профессия
Последний раз редактировалось MihalNik; 20.11.2016 в 17:42. Причина: Ссылка удалена |
20.11.2016, 17:48 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Проверять нечего. Ограничение в сумме 20 млрд. сопоставимо с ограничением в несколько десятков чисел: 2^35 > 20млрд.
Для 12 тыс. чисел задача экспоненциальна при размерности чисел где-то порядка 1Кб и более. Поэтому читать матан, хотя бы элементарную википедию, да.
Благими намерениями устлана дорога на programmersforum.ru
Последний раз редактировалось MihalNik; 20.11.2016 в 18:09. |
20.11.2016, 19:15 | #5 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
я понимаю, что с модераторами не спорят...
но все равно не пойму: задача имеет количество вариантов подлежащих перебору 2 в степени 12000. Ведь каждый предмет может быть взят или не взят... Матан продолжаю читать, но Вы ссылку то зачем удалили? Чтобы другие не тестировали? Из фриланса тему убрали, чтобы других мнений не было? Может кто-то бы из фрилансеров сказал, что за такие задачи не стоит браться... дешево... Прошу разрешения восстановить ссылку и тему во фрилансе.
помогать студентам - моя вторая профессия
|
20.11.2016, 19:19 | #6 |
Старожил
Регистрация: 12.01.2011
Сообщений: 19,500
|
С чего вдруг?
Наверно показалась рекламой вашего сайта.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом. |
20.11.2016, 19:30 | #7 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
Ссылка для рекламы моего сайта стоит в моих контактах. И ее никто не удаляет.
А здесь стояла ссылка на страницу со спорной программой <ссылку отправляете по запросу исполнителей им лично> У меня сомнения в ее практической ценности... Хотел услышать мнение экспертов... Если 10 человек скажут, что это тот же давно изобретенный "велосипед", то соглашусь...
помогать студентам - моя вторая профессия
Последний раз редактировалось MihalNik; 20.11.2016 в 20:35. |
20.11.2016, 20:30 | #8 | ||||
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Цитата:
Поясняю: берется 12000 чисел размерностью в 1 бит. Какая сложность задачи? Там максимум сумма 12000 и просто либо достаточно единичных бит, либо нет. Берётся 12000 чисел размерностью 2 бита... Вы не понимаете, что из 12000 чисел, например, в 32 или 64 разряда нельзя составить 2^12000 различных сумм? Их намного, намного меньше: 12000*(2^32 - 1) и 12000*(2^64 - 1) соответственно. Вещественные числа тоже ограничены в ёмкости. Цитата:
Цитата:
Цитата:
P.S.: в следующий раз внимательно читайте правила раздела и в соответствии с ними формулируйте свою задачу - за что Вы собираетесь заплатить
Благими намерениями устлана дорога на programmersforum.ru
Последний раз редактировалось MihalNik; 20.11.2016 в 21:18. |
||||
20.11.2016, 21:37 | #9 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
т.е. по Вашему, при количестве предметов n=10^4 задачу о рюкзаке 0-1 можно считать имеющей полиномиальный алгоритм решения?
Т.к. М (можно считать константой, ведь размерность то задачи n) много меньше чем (2^n)/n. Остается сложность О(2*10^14). Это похоже на правду...
помогать студентам - моя вторая профессия
|
20.11.2016, 21:46 | #10 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
Хотя парадокс...
Из этой логики получается, что при заданном константном М, чем выше n тем с большей вероятностью задача имеет полиномиальное решение?
помогать студентам - моя вторая профессия
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача о рюкзаке | Bugrimov | Общие вопросы C/C++ | 4 | 19.04.2014 05:10 |
Задача о Рюкзаке. | Lucid | Visual C++ | 3 | 07.11.2011 11:40 |
Задача о Рюкзаке. | Lucid | Помощь студентам | 0 | 07.11.2011 09:34 |
Задача о рюкзаке | VadEr | Помощь студентам | 6 | 16.09.2011 20:44 |