Comments 18
Для целых чисел существует алгоритм (динамическое программирование), который работает ЕМНИП за O(nW), где W — это значение контрольного числа.
Всё верно. А его в свою очередь можно ускорить в 32/64 раза по времени и памяти при помощи битового сжатия, если не требуется восстановление ответа (какие именно предметы мы взяли).
Но это, к сожалению, только для целых чисел. Задачу я сформулировал в целых числах, но это лишь для простоты примера. Впрочем, все исходные вещественные данные можно умножить, скажем, на 1000 (или на сколько памяти хватит), округлить, и считать уже динамическим программированием за O(nW). В Википедии это называется fully polynomial time approximation scheme. Я про всё это узнал уже после того, как запостил статью, но проблема меня по-прежнему волнует, и поэтому, вполне вероятно, я когда-нибудь напишу статью с анализом этого алгоритма.
Ассемблер и многопоточность не помогут сильно, сложность самого алгоритма по времени имеет гораздо большее значение.
Можно находить точно быстрее, чем за O(2n), используя идею Meet In The Middle, за O(2n/2logn), используя O(2n/2) памяти. То есть n=50 жует не задумываясь.
Идея простая как валенок: Берем половину предметов, для всех их подмножеств находим стоимости, записываем их в массив и сортим по суммарному размеру. Для каждого префикса массива находим макс. стоимость. Потом перебираем вторую половину и для каждого его подмножества ищем бинарным поиском в массиве префикс всех подмножеств второй половины, который еще «влазит» в рюкзак и смотрим максимальную стоимость по ним. Иии… вроде бы все.
Идея простая как валенок: Берем половину предметов, для всех их подмножеств находим стоимости, записываем их в массив и сортим по суммарному размеру. Для каждого префикса массива находим макс. стоимость. Потом перебираем вторую половину и для каждого его подмножества ищем бинарным поиском в массиве префикс всех подмножеств второй половины, который еще «влазит» в рюкзак и смотрим максимальную стоимость по ним. Иии… вроде бы все.
Прошу прощения, я слегка ошибся. Временная сложность будет O(2n/2n). Но n=50 оно все равно жует=)
Да, с n=50 должно справиться, но дальше мы стремительно приближаемся к имеющемуся объёму памяти. При n=54 нужно уже 4ГБ (если у нас есть и вес и стоимость, и оба они 64-битные), при n=56 — 8ГБ и т.д.
А бинарный поиск для второй половины ни к чему, достаточно идти двумя указателями по двум массивам навстречу (один увеличивать, другой уменьшать), и следить, чтобы сумма весов не превосходила предела.
После этого получится, что основное время ушло на сортировку (и генерация массивов, и поиск заняли O(2n/2)). Интересно, можно ли его уменьшить какой-нибудь радикс-сортировкой.
А бинарный поиск для второй половины ни к чему, достаточно идти двумя указателями по двум массивам навстречу (один увеличивать, другой уменьшать), и следить, чтобы сумма весов не превосходила предела.
После этого получится, что основное время ушло на сортировку (и генерация массивов, и поиск заняли O(2n/2)). Интересно, можно ли его уменьшить какой-нибудь радикс-сортировкой.
А, вы предлагаете 2 массива создать и посортить — тоже вариант. Я предлагал построить только один, а второй генерировать «на лету».
Для такого варианта, кстати, можно исходный массив делить на неравные части и меньшую использовать для генерации массива, пока лезет в память. Для большей части памяти не нужно, но работать это будет несколько дольше.
А вообще, чтобы на практике это работало быстрее — для большей части можно замутить какой-нибудь перебор с возвратом и отсечениями. Для практических задач — все летает, «крепкие орешки» почти не попадаются.
Для такого варианта, кстати, можно исходный массив делить на неравные части и меньшую использовать для генерации массива, пока лезет в память. Для большей части памяти не нужно, но работать это будет несколько дольше.
А вообще, чтобы на практике это работало быстрее — для большей части можно замутить какой-нибудь перебор с возвратом и отсечениями. Для практических задач — все летает, «крепкие орешки» почти не попадаются.
Компромисс времени и памяти, любопытно. Правда, для 50 входных чисел это получается 2 подмножества * 225 комбинаций * (8 байтов суммы + 8 байтов маски битов использованных чисел) = 1 ГБ памяти. Но до этих пределов действительно можно считать без свопинга.
Хм. А можно два ранца сразу собирать? В разных потоках…
А зачем тут код грея?
Если изначальный перебор делать рекурсией, считать сумму на лету и передавать ее дальше через стек, то сложность так и будет O(2n).
Кроме того, рекурсивный перебор позволит отсекать заведомо не подходящие комбинации (если сумма нескольких предметов уже больше целевого числа — смысла перебирать дальше нет).
Если изначальный перебор делать рекурсией, считать сумму на лету и передавать ее дальше через стек, то сложность так и будет O(2n).
Кроме того, рекурсивный перебор позволит отсекать заведомо не подходящие комбинации (если сумма нескольких предметов уже больше целевого числа — смысла перебирать дальше нет).
branch and bound knapsack
Не оно?
Не оно?
Sign up to leave a comment.
Задача о ранце и код Грея