задача о рюкзаке 0-1

[was3110]

Подскажите, пожалуйста, эксперты! Действительно ли, решение задачи о рюкзаке 0-1 можно рассматривать, как задачу нахождения быстрого (полиномиального) алгоритма для решения переборных задач? И за это деньги сулят? Или такие задачи не решаются для больших чисел? (допустим 12 тыс предметов и вес рюкзака 10 млрд)

[MihalNik]

https://ru.wikipedia.org/wiki/%D0%A0...B2_P_%D0%B8_NP

[was3110]

Не верите? Проверьте...<ссылка удалена>
Уважаемый, заслуженный модератор! После Вашей ссылки на Википедию народ шарахается от темы как от "вечного двигателя"...
Хоть бы один человек подтвердил, что "да... программа работает... и на тех данных, которые Википедия не считает реальными для решения".
Наверное, это Вам придется сделать... Чтобы не жалеть потом об упущенной возможности протянуть руку помощи нуждающемуся...

[MihalNik]

Проверять нечего. Ограничение в сумме 20 млрд. сопоставимо с ограничением в несколько десятков чисел: 2^35 > 20млрд.
Для 12 тыс. чисел задача экспоненциальна при размерности чисел где-то порядка 1Кб и более.
Поэтому читать матан, хотя бы элементарную википедию, да.

[was3110]

я понимаю, что с модераторами не спорят...
но все равно не пойму: задача имеет количество вариантов подлежащих перебору 2 в степени 12000.
Ведь каждый предмет может быть взят или не взят...
Матан продолжаю читать, но Вы ссылку то зачем удалили? Чтобы другие не тестировали? Из фриланса тему убрали, чтобы других мнений не было? Может кто-то бы из фрилансеров сказал, что за такие задачи не стоит браться... дешево...
Прошу разрешения восстановить ссылку и тему во фрилансе.

[Alex11223]

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

я понимаю, что с модераторами не спорят

С чего вдруг?

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

Вы ссылку то зачем удалили? Чтобы другие не тестировали?

Наверно показалась рекламой вашего сайта.

[was3110]

Ссылка для рекламы моего сайта стоит в моих контактах. И ее никто не удаляет.
А здесь стояла ссылка на страницу со спорной программой <ссылку отправляете по запросу исполнителей им лично>
У меня сомнения в ее практической ценности... Хотел услышать мнение экспертов...
Если 10 человек скажут, что это тот же давно изобретенный "велосипед", то соглашусь...

[MihalNik]

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

я понимаю, что с модераторами не спорят...
но все равно не пойму: задача имеет количество вариантов подлежащих перебору 2 в степени 12000.
Ведь каждый предмет может быть взят или не взят...

Нет, задача имеет сложность порядка O(min(N*M, 2^N)) - в существующей научной теории.
Поясняю: берется 12000 чисел размерностью в 1 бит. Какая сложность задачи? Там максимум сумма 12000 и просто либо достаточно единичных бит, либо нет. Берётся 12000 чисел размерностью 2 бита...
Вы не понимаете, что из 12000 чисел, например, в 32 или 64 разряда нельзя составить 2^12000 различных сумм? Их намного, намного меньше:
12000*(2^32 - 1) и 12000*(2^64 - 1) соответственно. Вещественные числа тоже ограничены в ёмкости.

Может кто-то бы из фрилансеров сказал, что за такие задачи не стоит браться... дешево...

Каких задач? Решить 1-ую проблему тысячелетия - таким задачам во фрилансе не место. Вы платите за проверку работы этой программы? Тогда - ссылку отправляете исполнителю, а я её отсюда удаляю и переношу обратно эту тему во фриланс. Да, там нет алгоритма, а есть программа которую предлагается потестировать. Т.е. спрашивается, укладывается ли исполняемая программа в рамки теории задачи о рюкзаке. Удачи жаждущим! Тема снова во фрилансе.

После Вашей ссылки на Википедию народ шарахается от темы как от "вечного двигателя"...

Наверное, потому что напоминает мошенничество?

Если 10 человек скажут, что это тот же давно изобретенный "велосипед", то соглашусь...

Вы готовы оплатить работу этих 10 человек?

P.S.: в следующий раз внимательно читайте правила раздела и в соответствии с ними формулируйте свою задачу - за что Вы собираетесь заплатить

[was3110]

т.е. по Вашему, при количестве предметов n=10^4 задачу о рюкзаке 0-1 можно считать имеющей полиномиальный алгоритм решения?
Т.к. М (можно считать константой, ведь размерность то задачи n) много меньше чем (2^n)/n.
Остается сложность О(2*10^14). Это похоже на правду...

[was3110]

Хотя парадокс...
Из этой логики получается, что при заданном константном М, чем выше n тем с большей вероятностью задача имеет полиномиальное решение?