Видимо, у вас не правильная оценка сложности. Сложность вашего алгоритма не (N*C)^K, где K — количество итераций, а N*C*K.
Все еще непонятно, почему безопасно брать все объекты до первого противоречия на этапе 4. Может быть, что вы случайно восстановите не нужный объект до того как найдете противоречие.
Но ваш алгоритм можно чуть чуть упростить и тогда все будет точно и легко доказано. Надо брать только один последний объект (LCr[Wr]) и затем снова возвращаться к этапу 2. Очевидно, что эта запись в массиве LCr не может быть переписана чем-то позже. Она и так последняя. Этот последний объект точно есть в ответе. Оценка сложности такого алгоритма будет N*C*N.
В целом ваша идея разменять большую потребность в памяти на более медленный алгоритм очень удачна.
Даже без этого упрощения сложность алгоритма остается такой же, т.к. итераций может быть сравнимо с N (их будет N/3 если взять и расширить мой указанный где-то в этой теме контр пример к первой версии алгоритма).
Советую вам или привести формальное доказательство корректности восстановления ответа, или изменить алгоритм, чтобы на каждой итерации (этапы 2,3,4) восстанавливать только один объект из ответа.
Не совсем понял, что происходит во второй версии алгоритма. То, что цена ответа будет правильной опять очевидно. Как восстанавливается набор элементов я не совсем понял.
Верно ли, что во время восстановления ответа, если видно, что надо взять уже взятый элемент, то восстановление останавливается и вы рекурсивно решаете задачу уже исключив взятые ранее элементы?
Да, к сожалению, единственный метод — это формальное доказательство правильности алгоритма. Или проверить на всех возможных входных данных, что почти всегда невозможно.
Наверно стоит изменить топик — дописать какой-то UPD или вообще убрать его в черновики.
Доказательство стоимости не надо, это очевидно. А вот второй пункт не верен.
Пример ниже совсем простой (С=7, W={3,5,2}, P={15,20,6}). В комментарии ниже я подробно разобрал, что происходит.
Вкратце, сортировка не спасает и массив LCr перезаписывается на более поздних итерациях.
Кстати, ваш алгоритм не правильно восстанавливает ответ.
Пусть веса объектов = {3, 5, 2}, а стоимости = {15, 20, 6}
Удельные стоимости = {5, 4, 3}
Пусть вместимость рюкзака С=7.
Итак, оптимальный набор, очевидно, последние 2 объекта (первые 2 просто в рюкзак не помещаются). И вы их найдете. Стоимость в ответе будет 26.
А вот с восстановлением ответа у вас будут проблемы.
На первой итерации (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) памяти.
Путаете. Не знаю, какую динамику вы имеете в виду, но при реализации стандартной динамики не надо хранить двумерный массив.
В динамике считается 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 тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
Формально, в динамике нужен двумерный массив размера N*C. Но это можно очевидно реализовать или храня только 2 строчки массива, или пересчитывая его на месте в одномерном массиве размера C. Это так просто в реализации, что двумерность параметров вспоминается, разве что, при доказательстве корректности алгоритма.
Странно, этот алгоритм и есть динамическое программирование. Может, не самая каноническая реализация решения задачи о рюкзаке, но абсолютно той же сложности и по времени и по памяти. Если стандартную динамику реализовывать лениво (снизу вверх), будет практически тоже самое.
У вас массив LP[j] на i-ой итерации — это максимальная стоимость подмножества первых i элементов весом j. LCr[j] — последний элемент в таком множестве. В стандартной динамике те же самые параметры и массивы.
Сортировка объектов по удельной стоимости и введение дополнительного массива Clone действительно являются эвристиками, позволяющими немного ускорить решение в некоторых случаях. Но от этого алгоритм не становится принципиально лучше динамики.
Эти идеи отлично применяются на практике. Например, NS-3 симулятор сети, который активно используется в научных исследованиях, сделан с использованием многих идей из этой книги. Там, например, Garbage Collector реализован через метапрограммирование в С++.
У меня нет ссылки, но я его видел прошлым летом своими глазами на pride parade в Сан Франциско в составе большой колонны с символикой Facebook'а. Он там еще печати «like» всем желающим ставил.
Гугл поиск по картинкам нашел это: www.businessinsider.com/mark-zuckerberg-gay-pride-parade-photos-2013-7
Хотелось бы сравнить с Дейкстрой на обычном CPU.
Дело в том, что сложность используемого алгоритма O(VE) в худшем случае. Сложность Дейкстры с кучей же O((V+E) logV )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Т.е. юрист Навальный просто идиот и не может корректно прочесть постановление следователя, и поэтому тупо пошел на риск, при условии, что следователя достаточно просто уведомить о выезде и никаких проблем не будет. С учетом, что за ним и так все время следят, смысла вот так что-то скрывать нет вообще.
Потом, что же ему меру пресечения-то не изменили? Нарушил же! Диссидент Навальный! Предположительно, вор, из семьи аферистов, да еще против царя батюшки выступает! Откуда такая гуманность у следствия?
Это просто пиар акция, чтобы создать шум. Заранее спланированная, с использованием административного ресурса и злоупотреблением полномочий подлость.
Кремлеботы все время акцентируют внимание на факте существования фирмы. Тот факт, что эта фирма практически упразднена с момента ее создания, и никогда никаких дел не вела как-то опускается. Я верю, что Навальный не лгал, а честно не знал что эта фирма существует.
В отличии от некоторых чиновников с подозрительными источниками доходов, которым ничиго не бывает даже после вскрытия оффшорных империй или элитных резиденций, скрытая фирма для Навального действительно несла неиллюзорные репутационные потери.
Не может человек, идущий против власти быть настолько идиотом, чтобы допускать такие риски, и при этом так долго быть такой помехой. Да, силовая машина абсолютно не эффективна (и даже при политической воле, не может нормально дело сшить), но если бы Навальный действительно что-то нарушал или скрывал — даже они бы смогли упечь его гораздо раньше.
удовлетворить ходатайство адвоката Кобзева В. Д. о разрешении его подзащитному Навальному А. А. выездов на территорию Московской области о совершении которых необходимо в обязательном порядке сообщать следователю
Еще раз: о совершении надо сообщать. Не о намерении, не заранее, не просить разрешения, а уведомить. Слова «после», «до» или какой-либо другой фразы о временных рамках в постановлении следователя нет.
Фраза «свободно выезжать на территорию Московской области» максимум немного неточна, но никак не ложь.
Вот те, кто его судят прямо лгут. Свидетели, на показаниях которых строится обвинение — прямо в суде были обличены во лжи, но судья это все просто проигнорировал.
Вы считаете, что в такой игрушечной модели нет смысла — но он есть. Для всех, кроме профессионалов, такая физическая модель будет гораздо более весомым аргументом, чем симуляция, хоть вы и говорите, что этой симуляции все профессионалы верят. Раз вы говорите, что модель тривиальная — почему бы ее не построить?
Все еще непонятно, почему безопасно брать все объекты до первого противоречия на этапе 4. Может быть, что вы случайно восстановите не нужный объект до того как найдете противоречие.
Но ваш алгоритм можно чуть чуть упростить и тогда все будет точно и легко доказано. Надо брать только один последний объект (LCr[Wr]) и затем снова возвращаться к этапу 2. Очевидно, что эта запись в массиве LCr не может быть переписана чем-то позже. Она и так последняя. Этот последний объект точно есть в ответе. Оценка сложности такого алгоритма будет N*C*N.
В целом ваша идея разменять большую потребность в памяти на более медленный алгоритм очень удачна.
Даже без этого упрощения сложность алгоритма остается такой же, т.к. итераций может быть сравнимо с N (их будет N/3 если взять и расширить мой указанный где-то в этой теме контр пример к первой версии алгоритма).
Советую вам или привести формальное доказательство корректности восстановления ответа, или изменить алгоритм, чтобы на каждой итерации (этапы 2,3,4) восстанавливать только один объект из ответа.
Верно ли, что во время восстановления ответа, если видно, что надо взять уже взятый элемент, то восстановление останавливается и вы рекурсивно решаете задачу уже исключив взятые ранее элементы?
Наверно стоит изменить топик — дописать какой-то UPD или вообще убрать его в черновики.
Пример ниже совсем простой (С=7, W={3,5,2}, P={15,20,6}). В комментарии ниже я подробно разобрал, что происходит.
Вкратце, сортировка не спасает и массив LCr перезаписывается на более поздних итерациях.
Пусть веса объектов = {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) памяти.
В динамике считается 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 тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
У вас массив LP[j] на i-ой итерации — это максимальная стоимость подмножества первых i элементов весом j. LCr[j] — последний элемент в таком множестве. В стандартной динамике те же самые параметры и массивы.
Сортировка объектов по удельной стоимости и введение дополнительного массива Clone действительно являются эвристиками, позволяющими немного ускорить решение в некоторых случаях. Но от этого алгоритм не становится принципиально лучше динамики.
Гугл поиск по картинкам нашел это:
www.businessinsider.com/mark-zuckerberg-gay-pride-parade-photos-2013-7
Дело в том, что сложность используемого алгоритма O(VE) в худшем случае. Сложность Дейкстры с кучей же O((V+E) logV )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Потом, что же ему меру пресечения-то не изменили? Нарушил же! Диссидент Навальный! Предположительно, вор, из семьи аферистов, да еще против царя батюшки выступает! Откуда такая гуманность у следствия?
Это просто пиар акция, чтобы создать шум. Заранее спланированная, с использованием административного ресурса и злоупотреблением полномочий подлость.
В отличии от некоторых чиновников с подозрительными источниками доходов, которым ничиго не бывает даже после вскрытия оффшорных империй или элитных резиденций, скрытая фирма для Навального действительно несла неиллюзорные репутационные потери.
Не может человек, идущий против власти быть настолько идиотом, чтобы допускать такие риски, и при этом так долго быть такой помехой. Да, силовая машина абсолютно не эффективна (и даже при политической воле, не может нормально дело сшить), но если бы Навальный действительно что-то нарушал или скрывал — даже они бы смогли упечь его гораздо раньше.
Еще раз: о совершении надо сообщать. Не о намерении, не заранее, не просить разрешения, а уведомить. Слова «после», «до» или какой-либо другой фразы о временных рамках в постановлении следователя нет.
Фраза «свободно выезжать на территорию Московской области» максимум немного неточна, но никак не ложь.
Вот те, кто его судят прямо лгут. Свидетели, на показаниях которых строится обвинение — прямо в суде были обличены во лжи, но судья это все просто проигнорировал.