Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 32
— Ваш алгоритм не полиномиальный, а только псевдополиномиальный, потому что в оценку сложности входит емкость рюкзака, которая может быть задана сколь угодно большой, например 10^100.
— В статье в википедии упоминается об алгоритме с аналогичными свойствами:
— В статье в википедии упоминается об алгоритме с аналогичными свойствами:
This solution will therefore run in O(nW) time and O(nW) space. Additionally, if we use only a 1-dimensional array m[w] to store the current optimal values and pass over this array i+1 times, rewriting from m[W] to m[1] every time, we get the same result for only O(W) space.
Тут проблема та же, что и с факторизацией. Т.е. да, чтобы найти множители числа N нужно всего-то сделать N делений — дайте мне премию Тьюринга! Но интересует нас алгоритм, полиномиальный отностительно количества бит в числе, и из-за этого вся путаница. В случае задачи о рюкзаке мозг выносит еще сильнее.
Прошу прощения, разве не ceil( N / 2 )? (каждое деление даёт пару чисел [делитель; частное], оставшиеся решения — те же пары в другом порядке)
Скажу больше. Достаточно до sqrt(N). Т.к. пускай существует число a > sqrt(N), на которое нацело делится N. Тогда возможны два варианта, либо N/a = b >sqrt(N), либо N/a=b <=sqrt(N). Первый случай невозможен, а во втором мы просмотрели бы уже число b, пробегая до sqrt(N).
Все равно N/2 = O(N) = O(2^k), Где k — длина входных данных (количество бит).
Я согласен c вами, просто для задачи о рюкзаке обычно неявно подразумевается, что емкость рюкзака С значительно меньше чем сумма весов. т.е. для бесконечной емкости рюкзака в него попадут все предметы. Самый тяжелый вариант когда емкость рюкзака С = Σ W / 2.Логика алгоритма рассчитана на стандартные типы данных, например:
long От -922 337 203 685 477 508 до 922 337 203 685 477 507
double От -1,797 693 134 862 32e308 до 1,797 693 134 862 32e308
Если C в них попадает, то все хорошо. Для очень больших C в пределах стандартных типов данных вместо массивов можно использовать списки и сложность тогда не будет явно зависеть от C, а скорее от длины списка.
Если для записи C не хватает стандартных типов данных, то все плохо.
long От -922 337 203 685 477 508 до 922 337 203 685 477 507
double От -1,797 693 134 862 32e308 до 1,797 693 134 862 32e308
Если C в них попадает, то все хорошо. Для очень больших C в пределах стандартных типов данных вместо массивов можно использовать списки и сложность тогда не будет явно зависеть от C, а скорее от длины списка.
Если для записи C не хватает стандартных типов данных, то все плохо.
Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
Никогда не слышал о ДП-методе решения задачи о рюкзаке не за
O(C) памяти. Как это делается?Формально, в динамике нужен двумерный массив размера N*C. Но это можно очевидно реализовать или храня только 2 строчки массива, или пересчитывая его на месте в одномерном массиве размера C. Это так просто в реализации, что двумерность параметров вспоминается, разве что, при доказательстве корректности алгоритма.
насколько мне известно, при решении задачи о рюкзаке методом ДП требуется двухмерный массив размера N * C, т.к. требуется восстановить решение. Возможно в методе ДП можно уменьшить двухмерного размерность массива, но видимо за счет дополнительных вычислений
В вашем методе тоже требуется двумерный массив для восстановления ответа. То, что написано у вас не работает. Контрпример я привел в комментарии ниже.
Извините, метод работает, я его проверял на нескольких десятков примеров, хотя это и не доказательство. Приду домой проверю ваш пример и отпишу, если хотите вышлю вам exe ( на VB6) Доказательство правильности состоит из двух этапов
1 в результирующем массиве всегда будет максимальная стоимость, доказывается по индукции.
2 результат восстанавливается по одномерному массиву, именно из за предварительной сортировки
1 в результирующем массиве всегда будет максимальная стоимость, доказывается по индукции.
2 результат восстанавливается по одномерному массиву, именно из за предварительной сортировки
Доказательство стоимости не надо, это очевидно. А вот второй пункт не верен.
Пример ниже совсем простой (С=7, W={3,5,2}, P={15,20,6}). В комментарии ниже я подробно разобрал, что происходит.
Вкратце, сортировка не спасает и массив LCr перезаписывается на более поздних итерациях.
Пример ниже совсем простой (С=7, W={3,5,2}, P={15,20,6}). В комментарии ниже я подробно разобрал, что происходит.
Вкратце, сортировка не спасает и массив LCr перезаписывается на более поздних итерациях.
Вот было бы как раз интересно узнать, чем же таким надо заполнить этот двухмерный массив, чтобы его надо было хранить целиком, чтобы восстановить ответ. Мне приходит в голову только искусственные схемы типа хранить в ячейке там 1 если для данной стоимости и данного номера объекта существует поднабор заданной стоимости, который может содержать объекты с номером не больше данного и обязательно содержит объект с данным номером.
Странно, этот алгоритм и есть динамическое программирование. Может, не самая каноническая реализация решения задачи о рюкзаке, но абсолютно той же сложности и по времени и по памяти. Если стандартную динамику реализовывать лениво (снизу вверх), будет практически тоже самое.
У вас массив LP[j] на i-ой итерации — это максимальная стоимость подмножества первых i элементов весом j. LCr[j] — последний элемент в таком множестве. В стандартной динамике те же самые параметры и массивы.
Сортировка объектов по удельной стоимости и введение дополнительного массива Clone действительно являются эвристиками, позволяющими немного ускорить решение в некоторых случаях. Но от этого алгоритм не становится принципиально лучше динамики.
У вас массив LP[j] на i-ой итерации — это максимальная стоимость подмножества первых i элементов весом j. LCr[j] — последний элемент в таком множестве. В стандартной динамике те же самые параметры и массивы.
Сортировка объектов по удельной стоимости и введение дополнительного массива Clone действительно являются эвристиками, позволяющими немного ускорить решение в некоторых случаях. Но от этого алгоритм не становится принципиально лучше динамики.
Становится. В каноничной реализации (по крайней мере, той, которую я считаю «каноничной») нам требуется O(nw) времени и столько же памяти. Здесь же память линейна, за счёт того, что мы для каждого веса храним только один способ его получить. При этом алгоритм хуже не становится — мы по-прежнему можем, пользуясь линейной памятью, восстановить набор предметов.
Путаете. Не знаю, какую динамику вы имеете в виду, но при реализации стандартной динамики не надо хранить двумерный массив.
В динамике считается L(i,j) — (самое дешевое подмножество из первых i объектов весом j). Пересчитывается очень просто L(i,j) = min(L(i-1,j), L(i-1, j-W(i))+C(i)). Достаточно хранить одну строку L(i, *), т.е. одномерный массив, и пересчитывать его с конца в начало.
Никогда на практике не сталкивался с реализацией динамики с O(NC) памяти. Да, времени надо O(NC), но в вашем алгоритме точно такая же оценка сложности: цикл по i до N, внутри цикл по j до С-W(i). Эвристики раннего завершения этапа 3 не влияют на оценку сложности ни в среднем ни в худшем случае. Параллелизация, которая доступна использовании дополнительного массива Clone тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
В динамике считается L(i,j) — (самое дешевое подмножество из первых i объектов весом j). Пересчитывается очень просто L(i,j) = min(L(i-1,j), L(i-1, j-W(i))+C(i)). Достаточно хранить одну строку L(i, *), т.е. одномерный массив, и пересчитывать его с конца в начало.
Никогда на практике не сталкивался с реализацией динамики с O(NC) памяти. Да, времени надо O(NC), но в вашем алгоритме точно такая же оценка сложности: цикл по i до N, внутри цикл по j до С-W(i). Эвристики раннего завершения этапа 3 не влияют на оценку сложности ни в среднем ни в худшем случае. Параллелизация, которая доступна использовании дополнительного массива Clone тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
«почему в учебниках по дискретной математике этого алгоритма нет»
Ну, тут есть, и я разбираю его со студентами, как пример практичного алгоритма, при определенных условиях для которого можно доказать полиномиальность в среднем.
Ну, тут есть, и я разбираю его со студентами, как пример практичного алгоритма, при определенных условиях для которого можно доказать полиномиальность в среднем.
PDF Кузюрина и Фомина я читал, но описания такого алгоритма не нашел. Видимо или PDF не тот, или искал плохо. Я писал в начале, что алгоритм уже известен, а всех книг по ДМ мне не прочитать.
Вот конкретно слайды и видеолекция с анализом в среднем алгоритма Н-У. Ну или на 145-й странице книги.
При всем моем уважении к вам и к Кузюрину, описания алгоритма на стр. 145 и ниже нет, там есть доказательство теоремы 12. Параграф называется
«Рюкзак»: полиномиальность в среднемЕсть ссылка на алгоритм 25 (Н-У) стр. 108, и далее ссылка на стр. 106 где приведен «стандартный» алгоритм ДП. Также я нигде не обнаружил предварительной сортировки ИД по уменьшению удельной стоимости, что является важной частью описанного в топике алгоритма.
А где почитать о задаче, где описаны геометрические размеры рюкзака (это может быть куб или паралелепипед) и вещей, которые тоже могут быть кубами и паралелепипедами и имеют разную ценность.?
Суть в том, что каждую вешь можно разместить в рюкзаке шестью разными способами, ну там лёжа на одной из трех граней, и под углом 0/90 градусов
Суть в том, что каждую вешь можно разместить в рюкзаке шестью разными способами, ну там лёжа на одной из трех граней, и под углом 0/90 градусов
это одномерный рюкзак, веса складываются, например 3 кг яблок + 2 кг апельсинов = 5 кг. Двухмерные и трехмерные упаковки это значительно сложнее. В квадрат 10 на 10 можно поместить прямоугольник 9 на 8, а 12 на 2 — нельзя. Насколько мне известно, для решения 2-3 мерных задач используются эвристики и ГА.
на хабре!
habrahabr.ru/company/infostart/blog/217369/
брут-форс решение задачи о рюкзаке с помощью SQL. Только без учета ценности, но мне кажется, это можно доработать.
habrahabr.ru/company/infostart/blog/217369/
брут-форс решение задачи о рюкзаке с помощью SQL. Только без учета ценности, но мне кажется, это можно доработать.
Кстати, ваш алгоритм не правильно восстанавливает ответ.
Пусть веса объектов = {3, 5, 2}, а стоимости = {15, 20, 6}
Удельные стоимости = {5, 4, 3}
Пусть вместимость рюкзака С=7.
Итак, оптимальный набор, очевидно, последние 2 объекта (первые 2 просто в рюкзак не помещаются). И вы их найдете. Стоимость в ответе будет 26.
А вот с восстановлением ответа у вас будут проблемы.
Перед циклом массивы будут
LP = {0, 0,0,15,0,0,0,0} // LP[3] == 15
LCr = {0, 0, 0, 1, 0, 0, 0, 0} // LCr[3] == 1
На первой итерации (i=2):
Сначала Сlone[5] станет 20
Затем в цикле по j мы ничего не найдем, т.к. С-W[i] = 7-5 = 2. А LP только в 3-ем элементе не 0.
После первой итерации массивы будут
LP = {0, 0, 0,15,0,20,0,0} // LP[5] == 20
LCr = {0, 0, 0, 1, 0, 2, 0, 0} // LCr[5] == 2
И, наконец, на последней итерации:
Сначала Сlone[2] станет 6.
В цикле по j от 2 до 5 мы найдем оба ненулевых LP.
Сделаем Clone[3+2] = Clone[5] = 15+6=21
Сделаем Clone[5+2] = Clone[7] = 20+6=26
после цикла по j, на мы перепишем LP[5] на 21 вместо 20 (испортив при этом LCr, который будет нужен при восстановлении ответа) и запишем LP[7]
Итоговые массивы будут:
LP = {0, 0, 0,15,0,21,0,26} // LP[5] == 21, LP[7] ==26
LCr = {0, 0, 0, 1, 0, 3, 0, 3} // LCr[5] == 3, LCr[7] ==3
При восстановлении ответа, мы найдем LP[7]=26, как ответ. Восстановим 3-ий объект, получим Wr=5. Но нужный нам LCr[5] был неправильно перезаписан на 2-ой итерации, и мы опять берем 3-ий объект, получив Wr=3. В итоге мы получим множество {3,3,1}, что не правильный ответ.
Нельзя обойтись одномерным массивом для восстановления ответа. Вы, видимо, думали, что сортировки по удельному весу будет достаточно, чтобы никогда нужный нам LCr не перезаписывался более поздними итерациями, но это не так. Если будете пытаться исправить алгоритм, убедитесь что он работает на примере с такими же предметами, но C=5 и С=8. В зависимости от размера рюкзака нам надо или нельзя перезаписывать LCr на более поздних итерациях.
Можно было бы попытаться хранить в LCr список всех возможных подмножеств, но такой подход очень быстро даст O(C*2^n) памяти.
Пусть веса объектов = {3, 5, 2}, а стоимости = {15, 20, 6}
Удельные стоимости = {5, 4, 3}
Пусть вместимость рюкзака С=7.
Итак, оптимальный набор, очевидно, последние 2 объекта (первые 2 просто в рюкзак не помещаются). И вы их найдете. Стоимость в ответе будет 26.
А вот с восстановлением ответа у вас будут проблемы.
Перед циклом массивы будут
LP = {0, 0,0,15,0,0,0,0} // LP[3] == 15
LCr = {0, 0, 0, 1, 0, 0, 0, 0} // LCr[3] == 1
На первой итерации (i=2):
Сначала Сlone[5] станет 20
Затем в цикле по j мы ничего не найдем, т.к. С-W[i] = 7-5 = 2. А LP только в 3-ем элементе не 0.
После первой итерации массивы будут
LP = {0, 0, 0,15,0,20,0,0} // LP[5] == 20
LCr = {0, 0, 0, 1, 0, 2, 0, 0} // LCr[5] == 2
И, наконец, на последней итерации:
Сначала Сlone[2] станет 6.
В цикле по j от 2 до 5 мы найдем оба ненулевых LP.
Сделаем Clone[3+2] = Clone[5] = 15+6=21
Сделаем Clone[5+2] = Clone[7] = 20+6=26
после цикла по j, на мы перепишем LP[5] на 21 вместо 20 (испортив при этом LCr, который будет нужен при восстановлении ответа) и запишем LP[7]
Итоговые массивы будут:
LP = {0, 0, 0,15,0,21,0,26} // LP[5] == 21, LP[7] ==26
LCr = {0, 0, 0, 1, 0, 3, 0, 3} // LCr[5] == 3, LCr[7] ==3
При восстановлении ответа, мы найдем LP[7]=26, как ответ. Восстановим 3-ий объект, получим Wr=5. Но нужный нам LCr[5] был неправильно перезаписан на 2-ой итерации, и мы опять берем 3-ий объект, получив Wr=3. В итоге мы получим множество {3,3,1}, что не правильный ответ.
Нельзя обойтись одномерным массивом для восстановления ответа. Вы, видимо, думали, что сортировки по удельному весу будет достаточно, чтобы никогда нужный нам LCr не перезаписывался более поздними итерациями, но это не так. Если будете пытаться исправить алгоритм, убедитесь что он работает на примере с такими же предметами, но C=5 и С=8. В зависимости от размера рюкзака нам надо или нельзя перезаписывать LCr на более поздних итерациях.
Можно было бы попытаться хранить в LCr список всех возможных подмножеств, но такой подход очень быстро даст O(C*2^n) памяти.
Вы правы, предложенный мной алгоритм содержит ошибку. Восстановить состав рюкзака с помощью одномерного массива LCr возможно не всегда. Ваш пример это доказывает. Первоначально LCr и был двухмерным ( C на N), но потом мне показалось что LCr можно сделать одномерным и сэкономить память, что даст алгоритму преимущество над методом ДП. Ошибся. Предлагаю дальнейшее обсуждение топика прекратить. Проверял алгоритм на разных наборах данных, вроде результаты получались правильные. Хорошее подтверждение тому, что экспериментальный метод в математике не работает.
Впервые услышал о данном алгоритме при просмотре сериала Числа, советую всем посмотреть, математикам в особенности!
Не совсем понял, что происходит во второй версии алгоритма. То, что цена ответа будет правильной опять очевидно. Как восстанавливается набор элементов я не совсем понял.
Верно ли, что во время восстановления ответа, если видно, что надо взять уже взятый элемент, то восстановление останавливается и вы рекурсивно решаете задачу уже исключив взятые ранее элементы?
Верно ли, что во время восстановления ответа, если видно, что надо взять уже взятый элемент, то восстановление останавливается и вы рекурсивно решаете задачу уже исключив взятые ранее элементы?
Видимо, у вас не правильная оценка сложности. Сложность вашего алгоритма не (N*C)^K, где K — количество итераций, а N*C*K.
Все еще непонятно, почему безопасно брать все объекты до первого противоречия на этапе 4. Может быть, что вы случайно восстановите не нужный объект до того как найдете противоречие.
Но ваш алгоритм можно чуть чуть упростить и тогда все будет точно и легко доказано. Надо брать только один последний объект (LCr[Wr]) и затем снова возвращаться к этапу 2. Очевидно, что эта запись в массиве LCr не может быть переписана чем-то позже. Она и так последняя. Этот последний объект точно есть в ответе. Оценка сложности такого алгоритма будет N*C*N.
В целом ваша идея разменять большую потребность в памяти на более медленный алгоритм очень удачна.
Даже без этого упрощения сложность алгоритма остается такой же, т.к. итераций может быть сравнимо с N (их будет N/3 если взять и расширить мой указанный где-то в этой теме контр пример к первой версии алгоритма).
Советую вам или привести формальное доказательство корректности восстановления ответа, или изменить алгоритм, чтобы на каждой итерации (этапы 2,3,4) восстанавливать только один объект из ответа.
Все еще непонятно, почему безопасно брать все объекты до первого противоречия на этапе 4. Может быть, что вы случайно восстановите не нужный объект до того как найдете противоречие.
Но ваш алгоритм можно чуть чуть упростить и тогда все будет точно и легко доказано. Надо брать только один последний объект (LCr[Wr]) и затем снова возвращаться к этапу 2. Очевидно, что эта запись в массиве LCr не может быть переписана чем-то позже. Она и так последняя. Этот последний объект точно есть в ответе. Оценка сложности такого алгоритма будет N*C*N.
В целом ваша идея разменять большую потребность в памяти на более медленный алгоритм очень удачна.
Даже без этого упрощения сложность алгоритма остается такой же, т.к. итераций может быть сравнимо с N (их будет N/3 если взять и расширить мой указанный где-то в этой теме контр пример к первой версии алгоритма).
Советую вам или привести формальное доказательство корректности восстановления ответа, или изменить алгоритм, чтобы на каждой итерации (этапы 2,3,4) восстанавливать только один объект из ответа.
Извиняюсь за задержку с ответом, был на даче. То что в указанном алгоритме на первой итерации значение LCr на максимуме LP будет правильно — очевидно. После сдвига вниз на вес найденного элемента мы или находим элемент существующий в Х или находим новый элемент не существующий в Х.
Во втором случае мы продолжаем спускаться вниз ( как и было в первой версии алгоритма) ничего не пересчитывая ( LP , LCr).
Первый случай возникает тогда, когда место, откуда мы прыгнули в максимум перезаписалось уже существующим в решении элементом. Тогда мы идем в рекурсию и снижаем число рассматриваемых элементов ИД + снижаем размер рюкзака. Из за предварительной сортировки по убыванию удельной стоимости необходимость в рекурсии будет не всегда ( например при попадании в точки, в которых LCr не изменялась). Вот если бы ИД были отсортированы по возрастанию удельной стоимости элементов, то на рекурсию мы бы попадали (наступали) почти на каждом шагу.
С вашей верхней оценкой временной сложности не более N*N*C согласен ( теоретически видимо возможен вариант ИД, когда итерацию будем делать на каждом шаге), со степенью я намудрил. Тем не менее, существуют наборы данных на которых итераций нет вообще и временная сложность =N*C. Как часто бывает, сложность алгоритма зависит от ИД.
Прошу не судить строго мои рассуждения, но мне кажется в алгоритме менять ничего больше не надо. Модифицировать алгоритм могут делать все желающие, желательно в лучшую сторону.
Я видимо не смогу формально доказать правильность восстановления решения на этапе 4. Я просто поделился алгоритмом, который требует меньше памяти чем стандартный алгоритм ДП в N раз или его потребность в памяти не зависит от N и применим в случае когда веса элементов вещественные, а не целые числа.
Во втором случае мы продолжаем спускаться вниз ( как и было в первой версии алгоритма) ничего не пересчитывая ( LP , LCr).
Первый случай возникает тогда, когда место, откуда мы прыгнули в максимум перезаписалось уже существующим в решении элементом. Тогда мы идем в рекурсию и снижаем число рассматриваемых элементов ИД + снижаем размер рюкзака. Из за предварительной сортировки по убыванию удельной стоимости необходимость в рекурсии будет не всегда ( например при попадании в точки, в которых LCr не изменялась). Вот если бы ИД были отсортированы по возрастанию удельной стоимости элементов, то на рекурсию мы бы попадали (наступали) почти на каждом шагу.
С вашей верхней оценкой временной сложности не более N*N*C согласен ( теоретически видимо возможен вариант ИД, когда итерацию будем делать на каждом шаге), со степенью я намудрил. Тем не менее, существуют наборы данных на которых итераций нет вообще и временная сложность =N*C. Как часто бывает, сложность алгоритма зависит от ИД.
Прошу не судить строго мои рассуждения, но мне кажется в алгоритме менять ничего больше не надо. Модифицировать алгоритм могут делать все желающие, желательно в лучшую сторону.
Я видимо не смогу формально доказать правильность восстановления решения на этапе 4. Я просто поделился алгоритмом, который требует меньше памяти чем стандартный алгоритм ДП в N раз или его потребность в памяти не зависит от N и применим в случае когда веса элементов вещественные, а не целые числа.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм решения задачи о рюкзаке ( версия 2, исправленная)