Pull to refresh
69
1.6
Илья @wataru

C++ разработчик.

Send message
Профессионала денег нанять не хватило — студент случайные задержки реализовать не додумался.
Не только книги есть. Например замечательное аниме «Space Fantasia 2001 Nights». В точности этот сюжет и рассказывает.
Финляндия: 20 евро 20Мбит, 25 — 50 мегабит. Никаких ограничений и резанья трафика.
Всего три различных исхода: перевесила одна чаша, перевесила вторая, обе чаши весят одинаково.
Декартово дерево требует больше памяти (обязательно по 2 указателя на элемент + сгенерированный случайно ключ для кучи).
Если цель — колонизировать планету, то нужны именно люди.
В аниме Space Fantasia 2001 Nights 1987 года именно эта идея показана.

Только там отправляли к далекой планете замороженные половые клетки, прицепив корабль к какой-то комете. По прилету, через много тысяч лет, клетки оплодотворялись и инкубировались, а андроиды на борту корабля новоиспеченных людей воспитывали.

Такой подход кажется более логичным, чем распиливание человеческого ДНК на части.
Видимо, у вас не правильная оценка сложности. Сложность вашего алгоритма не (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 перезаписывается на более поздних итерациях.
В вашем методе тоже требуется двумерный массив для восстановления ответа. То, что написано у вас не работает. Контрпример я привел в комментарии ниже.
Все равно N/2 = O(N) = O(2^k), Где k — длина входных данных (количество бит).
Кстати, ваш алгоритм не правильно восстанавливает ответ.
Пусть веса объектов = {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 тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
Формально, в динамике нужен двумерный массив размера 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
Простите, невнимательно прочитал статью. Это очень интересно, что оно настолько быстрее работает.

Information

Rating
1,355-th
Location
Stockholm, Stockholms Län, Швеция
Registered
Activity