Фактически вы запихали дополнительный массив, описанный в начале решения внутрь основного. Такое решение никак не может считаться решением без дополнительной памяти.
Это решение делает ровно те же перемещения по массиву, что и авторское. Автор, впрочем, также предложил метод нахождения описанного вами места без непосредственной перезаписи.
Вот было бы как раз интересно узнать, чем же таким надо заполнить этот двухмерный массив, чтобы его надо было хранить целиком, чтобы восстановить ответ. Мне приходит в голову только искусственные схемы типа хранить в ячейке там 1 если для данной стоимости и данного номера объекта существует поднабор заданной стоимости, который может содержать объекты с номером не больше данного и обязательно содержит объект с данным номером.
Нет, понятно, что можно хранить данные гораздо дольше, чем алгоритму требуется и так можно любой алгоритм сделать плохим по памяти. Вот если бы всю матрицу можно было бы как-то использовать при восстановлении множества — тогда я бы согласился, что алгоритм требует столько памяти.
Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
Никогда не слышал о ДП-методе решения задачи о рюкзаке не за O(C) памяти. Как это делается?
Кстати, на тимусе есть задачка с ровно таким же условием, так что если кто-то хочет проверить на скорую руку набросанное решение — он может сделать это в системе автоматической проверки: http://acm.timus.ru/problem.aspx?space=1&num=1378
Кто-нибудь из тех, кто шарит в ply, объясните мне, нафига не использовать именные пространства, а вместо этого использовать префиксы к названиям переменных и функций?
Вы немного неправильно поняли систему. Это при обычной системе собщения после отправки попадают в самый низ списка. При этой системе новые сообщения будут над уже заминусованными сообщениями той же ветки. Так что для новых сообщений будет только выигрыш.
А мне понравилась система сортировки комментариев, когда ветки комментариев на каждом уровне сортируются в порядке убывания рейтинга топового комментария. Т.е. на глобальном уровне висят сначала ветки с самыми заплюсованными топовыми комментариями, потом по убыванию, в комментариях к каждому комментарию используется та же система. В результате иерархия не ломается, ломается только хронология, но, как оказалось, не так уж часто надо знать, какой из одноуровневых комментариев был оставлен раньше.
Такая система используется на pikabu и больше я нигде такого не видел.
На рабочем только браузер и консоль (вся разработка в консоли). На домашнем много чего: есть и довольно требовательные игры и тяжелые среды типа Visual Studio и видео в хорошем качестве. Все это работает так же плавно, как и все, что есть на рабочем (что в общем логично, ram у них примерно одинаковая). Все это запускается не больше 5 секунд, но мне по роду деятельности не надо постоянно включать-выключать программы, а 5 секунд 5 раз за день совершенно не замечаются и нет никакого желания от них избавиться.
Никогда не слышал о ДП-методе решения задачи о рюкзаке не за
O(C)памяти. Как это делается?Такая система используется на pikabu и больше я нигде такого не видел.
На три дня. Если выключить функцию звонка, то на неделю.
P.S. Оба компа — ноутбуки