Кстати, ваш алгоритм не правильно восстанавливает ответ.
Пусть веса объектов = {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 )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Т.е. юрист Навальный просто идиот и не может корректно прочесть постановление следователя, и поэтому тупо пошел на риск, при условии, что следователя достаточно просто уведомить о выезде и никаких проблем не будет. С учетом, что за ним и так все время следят, смысла вот так что-то скрывать нет вообще.
Потом, что же ему меру пресечения-то не изменили? Нарушил же! Диссидент Навальный! Предположительно, вор, из семьи аферистов, да еще против царя батюшки выступает! Откуда такая гуманность у следствия?
Это просто пиар акция, чтобы создать шум. Заранее спланированная, с использованием административного ресурса и злоупотреблением полномочий подлость.
Кремлеботы все время акцентируют внимание на факте существования фирмы. Тот факт, что эта фирма практически упразднена с момента ее создания, и никогда никаких дел не вела как-то опускается. Я верю, что Навальный не лгал, а честно не знал что эта фирма существует.
В отличии от некоторых чиновников с подозрительными источниками доходов, которым ничиго не бывает даже после вскрытия оффшорных империй или элитных резиденций, скрытая фирма для Навального действительно несла неиллюзорные репутационные потери.
Не может человек, идущий против власти быть настолько идиотом, чтобы допускать такие риски, и при этом так долго быть такой помехой. Да, силовая машина абсолютно не эффективна (и даже при политической воле, не может нормально дело сшить), но если бы Навальный действительно что-то нарушал или скрывал — даже они бы смогли упечь его гораздо раньше.
удовлетворить ходатайство адвоката Кобзева В. Д. о разрешении его подзащитному Навальному А. А. выездов на территорию Московской области о совершении которых необходимо в обязательном порядке сообщать следователю
Еще раз: о совершении надо сообщать. Не о намерении, не заранее, не просить разрешения, а уведомить. Слова «после», «до» или какой-либо другой фразы о временных рамках в постановлении следователя нет.
Фраза «свободно выезжать на территорию Московской области» максимум немного неточна, но никак не ложь.
Вот те, кто его судят прямо лгут. Свидетели, на показаниях которых строится обвинение — прямо в суде были обличены во лжи, но судья это все просто проигнорировал.
Вы считаете, что в такой игрушечной модели нет смысла — но он есть. Для всех, кроме профессионалов, такая физическая модель будет гораздо более весомым аргументом, чем симуляция, хоть вы и говорите, что этой симуляции все профессионалы верят. Раз вы говорите, что модель тривиальная — почему бы ее не построить?
Мне не понятно, а где в законе о гос закупках записано, что обязательно должен быть аванс, что он должен быть какой-то определенной величины? Что мешает сделать тендер с минимальным авансом?
А что можно делать сейчас, если закон, все-таки никак не позволяет сделать то, что надо? Только способствовать изменению закона. А именно бороться с такими тендерами. Но делать это эффективно можно только откуда то сверху. Гражданам остается только прекратить оправдывать таких кадров.
Я как раз призываю поменять закон в сфере гос. закупок. А не закрывать глаза на кучу серых схем.
Опять же, в текущем примере никакие аргументы, что вот срочно надо, но без серых схем — никак, не проходят. Это никакая не срочная сфера. ЖКХ и без всяких компьютерных систем работает. Станет удобнее, эффективнее, но никаких проблем этот тендер не решит.
Именно позиция «ну фиг с ними, надо же пенсию платить и чинить трубы. Не стоит к ним негативно относиться» порождает порочный круг. Пока серые схемы есть — закон не меняется. Пока закон не меняется — нужны серые схемы. Если бороться с этими схемами, то порочный круг окажется разорван и чиновникам повыше, чтобы государство, таки, функционировало, придется поменять закон.
Самое простое — аванс выдается только фирмам с положительной историей контрактов. Для всех остальных полная сумма оплаты переводится после акта приемки, Еще можно разделить сумму на части и выдавать их после каждого этапа проекта.
Когда-то проскакивал пример о закупке медицинского оборудования, там, хотя бы, понятно, почему бывают сложности с корректной проводкой такой сложной операции. С софтом все проще. В текущем случае вообще не понятно, какие могут быть проблемы. Это портал в сети. Документация, проект, программный код — все это может выполнить одна фирма; все это в одну статью бюджета, вроде, входит.
Однако, если действительно есть какие-то проблемы, то их надо решать, а не обходить стороной. Нескоро примут новый закон? Не так просто изменить бюрократическую машину? Именно за это чиновники и получают зарплату. Да, видимо, заказчикам придется подождать. Но, если не будут на каждом углу городить серые схемы для обхода плохого закона, его придется улучшить. Зато совесть у участников процесса будет чище, а государственные деньги — целее.
Конкретно к текущему примеру — поставка софта не такая жизненно важная область, чтобы нужно было нарушать закон, чтобы побыстрее заключить контракт.
А что мешает тем же студентам из «Рога и Копыта» слиться с деньгами, ничего не делая, за 7 дней?
Такие нереальные сроки — именно чтобы отдать контракт кому-то конкретному, у кого уже все заранее готово.
Иногда пытаются такие схемы оправдывать тем, что таким образом выдерживаются какие-то устные договоренности и поставляются дополнительные услуги, которые, якобы, нельзя корректно провести через гос закупки. Но это все абсурд. «Нам неудобно работать по закону, который должен предотвращать коррупцию, поэтому мы воспользуемся схемой неотличимой от коррупции, не честной по человечески и противозаконной». Тут не может быть других интерпретаций.
Пусть веса объектов = {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 )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Потом, что же ему меру пресечения-то не изменили? Нарушил же! Диссидент Навальный! Предположительно, вор, из семьи аферистов, да еще против царя батюшки выступает! Откуда такая гуманность у следствия?
Это просто пиар акция, чтобы создать шум. Заранее спланированная, с использованием административного ресурса и злоупотреблением полномочий подлость.
В отличии от некоторых чиновников с подозрительными источниками доходов, которым ничиго не бывает даже после вскрытия оффшорных империй или элитных резиденций, скрытая фирма для Навального действительно несла неиллюзорные репутационные потери.
Не может человек, идущий против власти быть настолько идиотом, чтобы допускать такие риски, и при этом так долго быть такой помехой. Да, силовая машина абсолютно не эффективна (и даже при политической воле, не может нормально дело сшить), но если бы Навальный действительно что-то нарушал или скрывал — даже они бы смогли упечь его гораздо раньше.
Еще раз: о совершении надо сообщать. Не о намерении, не заранее, не просить разрешения, а уведомить. Слова «после», «до» или какой-либо другой фразы о временных рамках в постановлении следователя нет.
Фраза «свободно выезжать на территорию Московской области» максимум немного неточна, но никак не ложь.
Вот те, кто его судят прямо лгут. Свидетели, на показаниях которых строится обвинение — прямо в суде были обличены во лжи, но судья это все просто проигнорировал.
А что можно делать сейчас, если закон, все-таки никак не позволяет сделать то, что надо? Только способствовать изменению закона. А именно бороться с такими тендерами. Но делать это эффективно можно только откуда то сверху. Гражданам остается только прекратить оправдывать таких кадров.
Опять же, в текущем примере никакие аргументы, что вот срочно надо, но без серых схем — никак, не проходят. Это никакая не срочная сфера. ЖКХ и без всяких компьютерных систем работает. Станет удобнее, эффективнее, но никаких проблем этот тендер не решит.
Именно позиция «ну фиг с ними, надо же пенсию платить и чинить трубы. Не стоит к ним негативно относиться» порождает порочный круг. Пока серые схемы есть — закон не меняется. Пока закон не меняется — нужны серые схемы. Если бороться с этими схемами, то порочный круг окажется разорван и чиновникам повыше, чтобы государство, таки, функционировало, придется поменять закон.
Однако, если действительно есть какие-то проблемы, то их надо решать, а не обходить стороной. Нескоро примут новый закон? Не так просто изменить бюрократическую машину? Именно за это чиновники и получают зарплату. Да, видимо, заказчикам придется подождать. Но, если не будут на каждом углу городить серые схемы для обхода плохого закона, его придется улучшить. Зато совесть у участников процесса будет чище, а государственные деньги — целее.
Конкретно к текущему примеру — поставка софта не такая жизненно важная область, чтобы нужно было нарушать закон, чтобы побыстрее заключить контракт.
Такие нереальные сроки — именно чтобы отдать контракт кому-то конкретному, у кого уже все заранее готово.
Иногда пытаются такие схемы оправдывать тем, что таким образом выдерживаются какие-то устные договоренности и поставляются дополнительные услуги, которые, якобы, нельзя корректно провести через гос закупки. Но это все абсурд. «Нам неудобно работать по закону, который должен предотвращать коррупцию, поэтому мы воспользуемся схемой неотличимой от коррупции, не честной по человечески и противозаконной». Тут не может быть других интерпретаций.