Ресторан(10)

  • 15
  • Недоступна
Рекурсию используют тогда, когда алгоритм решения задачи совпадает с алгоритмом решения подзадачи (части). У нас как раз такой случай. Нам нужно сделать полный перебор всех вариантов и выбрать из них лучший. Напомню, рекурсия пишется по следующему принципу: а) условие выхода/окончания рекурсии б) у
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (124)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Леонид32 уровень, Москва
6 апреля, 10:26
А рекурсивным должен быть сам метод processVideos() или можно всю логику вынести во вспомогательный класс, а в processVideos() уже получить результат методов вспомогательного класса?
Kazbek34 уровень, Москва
31 марта, 14:48
В набор должны отбираться только ролики с положительным числом показов.
Долго не проходил этот пункт тут нашел код для теста вылетела ошибка деления на 0(hits), добавил проверку условия - валидатор принял 1904
Vitaly Khan36 уровень
20 марта, 22:46
задача напомнила Алгоритмы-числа (числа Армстронга в конце квеста Core). там тоже требовалось рекурсией перебрать все возможные варианты чисел, в которых цифры в числе идут по возрастанию. думаю, кто осилил ту задачу, смог сделать алгоритм и для этой.
20 марта, 13:48
5 попыток и куча времени. Самое сложное было написать метод отбора всех возможных вариантов. PoerSet от Василия помог). Посмотрю как дальше решение пойдёт
Vitaly Khan36 уровень
20 марта, 13:15
мне пришел в голову алгоритм, который показался очень простым (в отличие от рекурсии или динамического программирования). как же получить всевозможные комбинации из рекламных видео? если у нас N видеороликов, то комбинаций будет 2^N. можно заметить, что если перебрать все числа от 1 до 2^N-1 и представить их в двоичном виде, то они будут выглядеть так: 0...001 (всего N цифр) 0...010 0...011 0...100 ... 1...111 таким образом мы можем перебрать всевозможные комбинации из нулей и единиц. остается только для каждого такого значения сформировать новое подмножество рекламных видео. 1-й цифре соответствует 1-е видео, 2-й цифре - 2-е видео и т.д. до N. соответственно, если это 1, то видео добавляется в подмножество, если 0, то нет. если вы захотите попробовать этот алгоритм, вам пригодятся следующие приемы: 1) метод Integer.toBinaryString; 2) метод toCharArray класса String; 3) побитовое ИЛИ (|) и substring, чтобы сохранить нули вначале двоичного числа. например, у вас есть 0001, чтобы первые 3 нуля не пропали, нужно сделать побитовое ИЛИ с числом 2^N = 16 в нашем случае. тогда в бинарном виде мы получим 10001, его переводим в String, и только после этого отсекаем лишнюю единицу.
Vitaly Khan36 уровень
20 марта, 13:25
если надо, могу поделиться кодом...
CEO34 уровень
25 марта, 14:26
интересная идея, единственный недостаток, который приходит на ум это огромный объем памяти "остается только для каждого такого значения сформировать новое подмножество рекламных видео."© Как вариант решения, можно использовать 2 статические коллекции: лучшийНаДанныйМоментСет и текущийСет. Перед использованием затирать текущийСет. (не знаю, будет ли это эффективнее, чем создавать новый, у нас ведь есть сборщик мусора) А так идея и вправду интересная
CEO34 уровень
25 марта, 14:28
Еще, как вариант оптимизации, можно изначально ролики хранить в отсортированном виде по длительности, тогда после того момента, как текущийСет перестанет проходит проверку на время,
return;
Vitaly Khan36 уровень
26 марта, 10:27
да, я на самом деле так и реализовывал. не все подряд заносил в список множеств, а на лету проверял их суммарную длительность и их суммарную стоимость. это уже детали оптимизации. выше я просто ядро идеи изложил)
Dmitry Demikhov31 уровень, Самара
14 марта, 14:27
Тупил полдня, в итоге придумал алгоритм, но, проанализировав его, понял, что он не идеален, не все значения будут перебраны, при некоторых условиях. Пришлось лезть сюда. Оказывается , именно это решение от меня и ждут. Ну подсмотрел пару ключевых моментов по выводу строки на экран. В итоге запоролся на 3 сравнении, перепутал вывод местами и на том, что hits не должны равняться 0! А валик ругался на то, что он должен быть положительным. Ребяты, проверяйте всегда, на что вы делите)) Для сортировки массива сделал class Advertisement implements Comparable <Advertisement> и переопределил метод compareTo(Advertisement o), возврат Long.compare по amountPerOneDisplaying(o, this) и по mountPerOneDisplaying*1000/duration (this, o). Итого 3 попытки.1877 человек, а на предыдущей было 3 с чем-то тысячи, больше половины не справились.
Дмитрий41 уровень, Минск
14 марта, 13:19
Просто жесть, почитайте задачу про рюкзак поймите как это все работает и найдите решение на github. Вы решили задачу лучше, чем 10% учеников. Вам удалось ее решить с 24 попытки. Среднее количество попыток для этой задачи 10.22. Всего эту задачу решили 1876 учеников.
Artur41 уровень
27 февраля, 14:09
Сделал с помощью статьи, которую уже не раз скидывали сюда : Задача о рюкзаке. Чтение статьи и написание кода заняло где - то час времени, сам бы, конечно, не додумался до такого. Простая сортировка, которую предлагают тут может для валидатора и подходит, но сама по себе работает некорректно. Мы просто отбираем самые дорогие видео, не перебирая все возможные варианты: Пример: Общая Продолжительность 100 сек Видео 1 Стоимость 400 Продолжительность 100 сек Видео 2 Стоимость 210 Продолжительность 50 сек Видео 3 Стоимость 200 Продолжительность 50 сек Без рекурсии мы возьмем первое видео,что не верно, с ней же будет выбран нужный список p.s и да, без строки amountPerOneDisplaying = hits > 0 ? initialAmount / hits : 0 в конструкторе Advertisement валидатор не пускает дальше.
Евгений37 уровень, Москва
12 февраля, 15:24
Куча попыток в минус из-за собственной невнимательности: 2.4. Отобразить все рекламные ролики, отобранные для показа, в порядке уменьшения стоимости показа одного рекламного ролика в копейках. Вторичная сортировка - по увеличению стоимости показа одной секунды рекламного ролика в тысячных частях копейки. При этом валидатор ругался на 4-5 пункты.
Victoria Sedletskaya35 уровень, Одесса
17 января, 13:12
1817 человек 2 дня.. в Advertisement в toString выводила начальную стоимость вместо amountPerOneDisplaying за это время переписала создание списка тремя способами, внедрила все ваши советы из этого обсуждения, пробовала функцию создания списка со stakeoverflow, прочла про динамическое программирование, но решила еще последний раз вернуться к первоначальному решению (рюкзак) и походу заметила вывод initialAmount/100 (типа не в копейках, поэтому с выводом условия совпадало)