Валидатор не принимает решение задачи про "рюкзак"

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

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

Решен

Подскажите плз в чем проблема.

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

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

Текущее задание - реализовать п.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.kitchen.Cook; import com.javarush.task.task27.task2712.kitchen.Dish; import com.javarush.task.task27.task2712.kitchen.Waiter; public class Restaurant { public static void main(String[] args) { Tablet tablet = new Tablet(1); Cook cooker = new Cook("Jimmy"); tablet.addObserver(cooker); Waiter officiant = new Waiter(); cooker.addObserver(officiant); tablet.createOrder(); tablet.createOrder(); tablet.createOrder(); tablet.createOrder(); } }

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

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

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

Вадим

Уровень 35

18 июня 2022, 03:09

Господа, долго мучался с валидатором, проблема оказалась в том, что я не так округлял сотые доли: я делал вот так:

double db = (double) amountPerOneDisplaying/duration;
double dec = Math.abs(db - (int) db)*1000;
return (int) dec;

а надо:

return 1000 * amountPerOneDisplaying/ duration;

Будьте внимательны, из-за этого у меня не проходили первые два пункта. Не считаю это правильным, потому что при этом решении, если мы возьмем Long.MAX_VALUE у нас в ответе hits будут отрицательные.

Зенур

Уровень 39

26 ноября 2020, 19:53

Я переписал так: if (calcDuration(list) <= timeSeconds && (calcAmountList > bestAmount || (calcAmountList == bestAmount && calcDuration(list) > calcDuration(bestList)) || (calcAmountList == bestAmount && calcDuration(list) == calcDuration(bestList)) && list.size() < bestList.size())) { bestList = list; bestAmount = calcAmountList; }

Anonymous #1964998

Уровень 41

16 марта 2020, 00:06

Знакомое решение )))

Ola Backend Developer

17 марта 2020, 18:05

ну я точно не свое тут писал ) пытался динамическим программированием, но чет сдался. надо попробовать снова )

Ola Backend Developer

24 января 2019, 10:15

решение

Задача решилась добавлением сортировки перед выводом рекламы. Хз, почему так. Человек , заглянувший сюда и решивший разобраться, подскажи плз ПОЧЕМУ ОНО ТАК?

bestAdvertisements
.sort(Comparator.comparingLong(Advertisement::getAmountPerOneDisplaying)
.thenComparingInt(Advertisement::getDuration)
.reversed());

+11

Ilya Klishin

Уровень 41

12 ноября 2019, 17:04

Спасибо! А то я уже отчаялся...

Ola Backend Developer

15 ноября 2019, 06:02

то еще приключение, да? xD

Don Fear

Уровень 41

13 февраля 2020, 07:58

Окончательная сортировка перед выводом нужна чтоб убедиться, что мы соответствуем условиям. "4. если существует несколько вариантов набора видео-роликов с одинаковой суммой денег, полученной от показов, то: 4.1. выбрать тот вариант, у которого суммарное время максимальное; 4.2. если суммарное время у этих вариантов одинаковое, то выбрать вариант с минимальным количеством роликов;" Без этой сортировки ваш алгоритм выдает обратный порядок видеороликов. PS: не смотря на то что мой вариант сразу выдавал верный результат, валидатор безапелляционно потребовал наличий данной сортировки.