Timeout при проверке. Выборка реклам.

Вопрос по задаче

Java Multithreading, 9 уровень, 15 лекция

Решен

Доброго времени суток. Бьюсь уже какую неделю над задачей, просто уснуть не дает. Все никак не могу прийти к алгоритму который валидатор сумеет проверить. Итак что конкретно происходит: Беру первоначальный список, и удаляю из него все рекламы, которые превышают общее время заказа по времени, и с нулевым hits. Отдаю в функцию полученый лист. Функция(setBestList): Проверяем есть ли у нас уже какая-нибудь определенная комбинация: Если нет: Проверяем что общее время реклам < общего времени готовки. Если да - запоминаем как лучшую комбинацию. Запоминаем ее параметры(Время прокрутки, цены, кол-во реклам в блоке) Если нет - Для каждого элемента листа вызываем setBestList, передавая в него тот же лист, но с удаленным текущим элементом. Если есть уже определенный "лучший набор": Проверяем что текущий лист лучше чем "лучший набор"(по условию, сверяем стоимость рекламы>время прокрутки>количество реклам в блоке). Если текущий лист лучше "лучшего листа" то проверяем пройдет ли по времени заказа. Если да => переопределяем "лучший набор" Запоминаем его параметры. Если нет => опять начинаем рекусивно крутить удаляя по элементу и вызывая эту же функцию. Полученый результат сортирую выдачу по условию. На домашней машине все работает мгновенно на ростер из 10+ реклам с нарандомлеными параметрами. Я не знаю сколько они там кидают в джавараше нагруз, но я официально сдаюсь. Сижу над этой задачей уже месяц. Я уже не знаю куда алгоритм оптимизировать.

Рекурсию используют тогда, когда алгоритм решения задачи совпадает с алгоритмом решения подзадачи (части).
У нас как раз такой случай. Нам нужно сделать полный перебор всех вариантов и выбрать из них лучший.

Напомню, рекурсия пишется по следующему принципу:
а) условие выхода/окончания рекурсии
б) условие продолжения - вызов самой себя с набором параметров предыдущего шага.
В любое время ты можешь почитать в инете подробную информацию по написанию рекурсии.

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

Этот набор должен удовлетворять следующим требованиям:
1. сумма денег, полученная от показов, должна быть максимальной из всех возможных вариантов
2. общее время показа рекламных роликов НЕ должно превышать время приготовления блюд для текущего заказа;
3. для одного заказа любой видео-ролик показывается не более одного раза;
4. если существует несколько вариантов набора видео-роликов с одинаковой суммой денег, полученной от показов, то:
4.1. выбрать тот вариант, у которого суммарное время максимальное;
4.2. если суммарное время у этих вариантов одинаковое, то выбрать вариант с минимальным количеством роликов;
5. количество показов у любого рекламного ролика из набора - положительное число.

Также не забудь реализовать п.2.4 из предыдущего задания (вывести на экран все подходящие ролики в порядке уменьшения стоимости показа одного рекламного ролика в копейках. Вторичная сортировка - по увеличению стоимости показа одной секунды рекламного ролика в тысячных частях копейки).

Для каждого показанного видео-ролика должен быть вызван метод revalidate().

Требования:

Сумма денег, полученная от показов, должна быть максимальной из всех возможных вариантов.
Общее время показа рекламных роликов НЕ должно превышать время приготовления блюд для текущего заказа.
Для одного заказа любой видео-ролик должен показываться не более одного раза.
Если существует несколько вариантов набора видео-роликов с одинаковой суммой денег, полученной от показов, то должен быть выбран вариант с максимальным суммарным временем.
Если существует несколько вариантов набора видео-роликов с одинаковой суммой денег и одинаковым суммарным временем, то должен быть выбран вариант с минимальным количеством роликов.
В набор должны отбираться только ролики с положительным числом показов.
Для каждого показанного ролика должен быть вызван метод revalidate.

package com.javarush.task.task27.task2712; import com.javarush.task.task27.task2712.ad.AdvertisementManager; import com.javarush.task.task27.task2712.kitchen.Cook; import com.javarush.task.task27.task2712.kitchen.Dish; import com.javarush.task.task27.task2712.kitchen.Order; import com.javarush.task.task27.task2712.kitchen.Waiter; import java.io.IOException; import java.util.List; public class Restaurant { public static void main(String[] args) throws IOException { Cook cook = new Cook("TestCook"); Tablet tablet1 = new Tablet(1); tablet1.addObserver(cook); Waiter waiter = new Waiter(); cook.addObserver(waiter); tablet1.createOrder(); } }

Комментарии (7)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Александр Колосов

Уровень 36

13 марта 2019, 08:58

У меня не пропускало решение с использованием метода getHits(). Сделал, как у Вас, с проверкой в конструкторе if (hits > 0). К тому же, мне так и не удалось понять, почему валидатор так требователен к строке вывода ролика на экран. Если это так важно, то почему в условии не приведен пример, не понятно.

Максим Кобыляков

Уровень 41

8 ноября 2018, 01:57

Обычно чудес не бывает - раз говорят зависла следовательно ищи "вечный" цикл

Вечный Воитель

Уровень 31

4 ноября 2018, 19:43

Для пример тест: Рекламы add(new Advertisement(someContent, "First Video", 2842, 1, 5 * 60));; add(new Advertisement(someContent, "Second Video", 4019, 1, 32 * 60)); add(new Advertisement(someContent, "Third Video", 343, 1, 40 * 60)); add(new Advertisement(someContent, "Fourth Video", 123, 1, 30 * 60)); add(new Advertisement(someContent, "Fifth Video", 3891, 1, 2 * 60)); add(new Advertisement(someContent, "Seventh Video", 2561, 1, 20 * 60)); add(new Advertisement(someContent, "Eight Video", 3038, 1, 36 * 60)); add(new Advertisement(someContent, "Ninth Video", 606, 1, 28 * 60)); add(new Advertisement(someContent, "Ten Video", 4508, 1, 18 * 60)); Выберите блюдо: Fish, Steak, Soup, Juice, Water, Soup Soup Soup Water exit Your order: [Soup, Soup, Soup, Water] of Tablet{number=1} Start cooking - Your order: [Soup, Soup, Soup, Water] of Tablet{number=1}, cooking time 48min Your order: [Soup, Soup, Soup, Water] of Tablet{number=1} was cooked by TestCook Seventh Video is displaying... 2561, 468 First Video is displaying... 2842, 105 Fifth Video is displaying... 3891, 30 Ten Video is displaying... 4508, 239

Антон Кашников Java Developer

9 ноября 2018, 08:05

1. Компаратор написан неправильно

public int compare(Advertisement o1, Advertisement o2) {
              if (o1.getAmountPerOneDisplaying() > o2.getAmountPerOneDisplaying()) return 1;
              else if (o1.getAmountPerOneDisplaying() == o2.getAmountPerOneDisplaying()){
                  if ((double) (o1.getDuration() / o1.getAmountPerOneDisplaying()) > (double) (o2.getDuration() / o2.getAmountPerOneDisplaying())) return 1;
                  else return -1;
              }else return -1;
          }

Нужно с точностью наоборот. Поменяй -1 и 1 местами. 2. Класс-обёртка Integer, хоть и поддерживает автобоксинг, сравнивать значения нужно через .equls(). Или вызывать метод .intValue() чтобы получить интовое значение. Поэтому код отрабатывает не правильно.

if (mapParams.get("cash") < bestListParams.get("cash")) {
           return false;
       } else if (mapParams.get("cash") == bestListParams.get("cash")) {
           if (mapParams.get("commonDuration") > bestListParams.get("commonDuration")) {
               return true;
           } else if (mapParams.get("commonDuration") == bestListParams.get("commonDuration")) {
               if (mapParams.get("count") < bestListParams.get("count")) {
                   return true;
               } else return false;
           } else return false;
       } else return true;
   }

Антон Кашников Java Developer

9 ноября 2018, 08:06

3. Непрвильно переопределен метод toString() . Попробуй так:

@Override
public String toString() {
    return String.format("%s is displaying... %d, %d",name,getAmountPerOneDisplaying(),(1000 * getAmountPerOneDisplaying() / getDuration()));
}

Антон Кашников Java Developer

9 ноября 2018, 08:08

решение

4. И самое главное. В классе AdvertisementStorage. Данные должны быть проинициализированы один раз. Тоесть, в конструкторе, а не при каждом вызове getInstance() . Я исправил вышеперечисленное и у мене прошло.

Вечный Воитель

Уровень 31

9 ноября 2018, 20:27

ОГРОМНОЕ СПАСИБО. Особенно за конструктор. Стоило его сменить - перестало с таймаутом падать.