Ресторан(10)

  • 32
  • Недоступна
Рекурсию используют тогда, когда алгоритм решения задачи совпадает с алгоритмом решения подзадачи (части). У нас как раз такой случай. Нам нужно сделать полный перебор всех вариантов и выбрать из них лучший. Напомню, рекурсия пишется по следующему принципу: а) условие выхода/окончания рекурсии б) у
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (257)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
LuneFox богатый программист в далёких мечтах Expert
25 ноября, 16:20
Хм... сделал, закрыв не совсем все условия, но валидатор принял. 0) Создаю в классе список, который будет хранить ролики для показа. 1) Пишу компаратор, который выводит сначала самые оплачиваемые ролики. 2) Пишу метод, который делает следующее: - сортирует список из хранилища по компаратору - для каждого видео в списке, если оно умещается по времени, а также имеет положительное количество оставшихся просмотров и ещё не находится в списке для показа, добавляю его в список роликов для показа, также добавляю в свежесозданный вспомогательный список - если в конце работы метода вспомогательный список не пустой, рекурсивно вызываю этот же метод - когда больше никакие ролики не подойдут, вспомогательный список окажется пустым и метод завершится 3) Сортирую получившийся список на показ ещё раз по тому же самому компаратору. Сдал с 3-й попытки - в первый раз забыл убрать временную строчку, которую выводил в консоль, второй раз забыл не показывать видео, число оплаченных просмотров которых закончилось.
Valerii
Уровень 31, Москва, Россия
20 ноября, 22:50
Для понимания того как решать такие задачи очень помогло это видео Видео Там есть ссылка на гит и решение всяких разных похожих задач.
Den is
Уровень 30, Москва, Россия
17 ноября, 11:16
чокнутый валидатор. Мучил меня, когда уже результат был правильный, но по двум пунктам не пропускал. Искал решения и так и эдак и вот сделал откат решения, нажал на проверку и о чудо! Взял и принял. Ничего не понимаю, но главное прорвался!
Максим Дудин
Уровень 31, Калининград
27 октября, 17:07
решил в меру понятия, проверил по мере возможности на соответствие всем требованиям, всё как в выводе. Гарантировано не прошёл валидацию... скопировал готовое решение (иначе это уже всё слишком на долго затягивается 2,5 недели) ну вот разве что надо будет всё таки в готово решении разобраться что и почему как
RFedorenkov
Уровень 47, Москва, Россия
28 октября, 18:47
Совет Если копируешь готовое решение, то на последнем уровне сбрось прогресс и попробуй решить задачу самому, пусть даже через пару месяцев. Она не очень сложная. p.s. дальше хуже будет)))) особенно на стажировке (думаю забить до следующей)
Evgeny
Уровень 31, Владимир
29 сентября, 07:48
Получилось по принципу "рюкзака"! Комментарий Maxim Dimitrov помог не улетать в тайм-аут при проверке!
Andrey
Уровень 51
23 сентября, 08:22
Часа два разбирался с алгоритмом, решил делать через рюкзак, сделал, все работает, валя не принимает по 1 и 4 пунктам. Начал разбираться, улучшил алгоритм, сделал доп проверки перед рекурсией. У меня все работает, у вали опять 1 и 4. Ломал голову, почитал кучу постов отсюда, ничего не помогает. Плюнул, разобрался в "правильном решении", изначально в эту сторону думал, переделал кучу кода, а валя непреклонен. В итоге убил целый день.20 попыток. А проблема оказалась в сортировке уже правильно отобранного списка. Вот так не принимал.
bestList.stream().sorted(
        Comparator.comparingLong(Advertisement::getAmountPerOneDisplaying).reversed()
        .thenComparingLong(a -> a.getAmountPerOneDisplaying() / a.getDuration()));
А вот так можно.
bestList.sort((o1, o2) -> {
            long l = o2.getAmountPerOneDisplaying() - o1.getAmountPerOneDisplaying();
            return (int) (l != 0 ? l : o2.getDuration() - o1.getDuration());
        });
Я не очень со стримами и лябдами дружу, кто в теме, подскажите, это прихоть вали, или действительно не так сортирует, как надо. Вывод: Валидатор показывает и дает рекомендации совсем не на те места, которые ему не нравятся, придется угадывать здесь самому, почему он капризничает. Обращение к создателям. Если вы в задаче не в состоянии наладить подсказки валидатора, уберите их совсем......
Галкин Юрий
Уровень 33, Москва
22 ноября, 12:03
a -> a.getAmountPerOneDisplaying() / a.getDuration()
o2.getDuration() - o1.getDuration()
это же разные вычисления: одно по длительности, другое по отноешению некоторой величины к длительности...
Andrey
Уровень 51
23 ноября, 09:17
Да, точно. Понял, что за 2 месяца забыл совершенно, что там в задаче. И почему я так делал, а не иначе
12 сентября, 12:14
Решил через динамическое программирование. Сначала в массиве хранил листы -- ну, удобно же, не надо делать "обратный ход" всё готовенькое лежит в последнем столбце :) Это оказалось ооочень ресурсоёмким решением, которое приводило к тайм-ауту. Поэтому вернулся к классике: прямой ход (заполняем массив, где строки это видеоролики, столбцы это секунды, числами), обратный ход (для каждой строки из последнего столбца восстанавливаем список использованных видеороликов). Потом проверки готовых решений на 4.1, 4.2 и сортировка из прошлых пунктов. Задача отличная, заставила подумать. Не халявьте, отправляя жадные алгоритмы (валидатор и их примет) :)
Maxim Dimitrov
Уровень 35
25 августа, 17:46
Подсказка для тех, кто делает через рекурсию и улетает в тайм-аут при валидации: При каждой итерации проверяйте, может ли ваш текущий вариант оказаться оптимальным по цене, или уже нет. Если нет, обрубайте ветку итерации, это сокращает время.
RFedorenkov
Уровень 47, Москва, Россия
24 августа, 08:19
Не получилось решить с помощью рюкзака (рекурсивный подход), уходил в бесконечность. Период ожидания при роликах 10 штук около 2 минут. Пробовал создавать отдельный список, где есть только hits > 0 и потом использовать его в качестве подбора, но не получилось. Ожидание слишком высокое. Как решил я. Во 1-х переопределил toString() в соответствии с выводом в задании
First Video is displaying... 50, 277
2) Имплемитировал Comparable<Advertisement> и переопределил метод compareTo(), который сравнивнивает по уменьшению стоимости одного показа и если стоимость одинаковая, то сравнивает по увеличению стоимости показа одной секунды рекламного ролика в тысячных частях копейки. 3) Сделал отдельный метод, который вычисляет стоимость показа рекламного ролика в тысячных частях копейки
amountPerOneDisplaying * 1000 / duration;
4) В самом решении использовал "жадный алгоритм". В отсортированном списке добавлял ролики до тех пор, пока время позволяло. Несколько попыток потерял из-за того, что запускал валидацию не с корневого файла, а с пакета ad класс AdvertisementManager. В результате выдавал ошибку:
Ошибка в файле com/javarush/task/task27/task2712/ad/AdvertisementManager.java в строке :  3
Не могу найти описание класса "ConsoleHelper" в packageе "com.javarush.task.task27.task2712". Возможно вы забыли его импортировать (указать в import)
Видимо какой то баг. Итого 9 попыток. -1162 участников на 10 задании. | 29% | 3343 | (8.76) |
Иван
Уровень 41, Москва
21 августа, 09:10
Задача решена, за алгоритм спасибо Кириллу и задачу про рюкзак. Что не понравилось, перебор в алгоритме достаточно однобокий, попытка исправить такое поведение с более полным перебором ведёт к превышению времени работы алгоритма, в итоге существует совсем не хилая вероятность пропустить нужную комбинацию. Так же есть большая претензия к составителям задачи, а именно к тестовым данным и форматам хранения, в частности возможна комбинация, при которой показ вообще ни чего не стоит и в итоге ролик мы просто не показываем, хотя количество показов сильно больше нуля.