Ресторан(10)

После этой задачи - Валидатор обязан на мне Жениться!!!!! У кого не проходит по 4 5 пункту - и вы со всех сторон облизали вывод, и проверили все запятые, условия, знаки равенства - не равенства, прочитали все ненаписанные книги про Компаратор.... Скажу только что меня спасло только переделывание с ноля строго по принципу этого долбанного рюкзака без излишней фантазии....

Эту задачу нужно было разбить на 10 подзадач с подробной инструкцией с поясняющими материалами, в результате получился бы интересный учебный материал знакомящий обучающегося с возможными способа использования рекурсии, а так же с вариантами использования сложных логических условий для решения нестандартных задач требую.щий сложных вычислений. А сейчас это просто головоломка (которая вообще не решается без хорошего понимания математической стороны задачи), предлагающая ученику на пару недель выпасть из учебного процесса чтобы... скорее всего все равно не решить задачу. Даже готовое решение выглядит крайне сложным для понимания и извлечь из него пользу и знания о способах построение программ будет ох как непросто.

А если в ArrayList добавлять первый ролик в конец, а из начала убирать? Таким образом перебрать все варианты получится?

private   ArrayList<Advertisement> storageList = (ArrayList<Advertisement>) storage.list();
private  ArrayList<List<Advertisement>> advList = new ArrayList<>();

private ArrayList<ArrayList<Advertisement>>  myAllOptions(){
        for(int i = 0; i < storageList.size()  ; i++){
            storageList.add(storageList.get(0));
            storageList.remove(0);
            advList.add(new ArrayList<>(storageList));
        }
    }

1) Сначала надо разобраться с задачей про рюкзак; 2) Сделать новый список, где hits>0; 3) Алгоритм помещает в массив первое оптимальное значение из нашего списка - соответственно, нужно предварительно отсортировать список по убыванию длительности 4) пускаем наш список в алгоритм рюкзака- на выход получаем новый 5) делаем сортировку как нас просят в задаче 6) revalidate

Задачу оптимизации из курса матана/сисанала давать чайникам - это сильно. Еще и сходники подковерканные, тут связанный список и без него не собирается, там внезапно вложенный класс появился. Не, это днище Всего эту задачу решили 3920 учеников. Отвалилось 1639 человек , по сравнению с 5м этапом и их можно понять.

Если кто-то решит все-таки попробовать решить рекурсией рекомендую: 1, 2 По сути задача выбора оптимального набора роликов сводится к комбинаторике: получаем все возможные наборы роликов (длина набора от 1 до X, где X - длина массива в AdvertisementStorage). Отбрасываем те комбинации, которые не подходят по суммарной длине. Остальные добавляем в List. Для удобства советую воспользоваться преимуществами наследования и создать AdvertisementSet:

public class AdvertisementSet extends HashSet<Advertisement> implements Comparable<AdvertisementSet> {
    private int duration = 0;
    private long amountPerDisplay = 0L;

    ....
}

После того как сформировали все допустимые наборы видео в List<AdvertisementSet>, его необходимо отсортировать, для этого вспоминаем Comparator, Comparable...

Всего эту задачу решили 3886 учеников. Убила кучу времени на то, чтобы разобраться в решении задачи о рюкзаке методом динамического программирования. Почитала комменты, чтобы избежать типичных ошибок, в результате сдала с первого раза. Из того, что мне показалось важным для решения этой задачи: 1. Из всех видео оставила только те, где hits > 0. 2. Отсортировала оставшиеся видео по убыванию длительности (понадобится при восстановлении ответа). 3. Построила массив, где в строках видео, а в столбцах - секунды (да, столбцов будет очень много, если время готовки продолжительное). 4. Восстановила ответ. Если у вас есть несколько видео с одинаковой стоимостью, но разной длительностью, при восстановлении ответа всегда будет выбираться то, которое в списке шло первым. Для этого сортировка в пункте 2. 5. Отсортировала итоговый список по условию. Мой компаратор:

Comparator<Advertisement> comparator = Comparator.comparing(Advertisement::getAmountPerOneDisplaying, Comparator.reverseOrder())
                .thenComparing(Advertisement::getAmountPerOneSecondOfDisplaying);

аmountPerOneSecondOfDisplaying - сделала отдельным свойством класса Advertisment, рассчитывала в конструкторе. Дальше всё банально. Не забудьте про revalidate() На всё ушло 8 дней (могу заниматься не больше двух часов в день). Уважаю тех, кто пишет, что им хватило 2х часов, чтобы разобраться в алгоритме.

Застрял на 14 задаче и потому решил начать весь проект заново. К написанию кода для 10 задачи решил подойти более осмысленно и сделать все как можно аккуратнее. Итог - валидатор принял с первой попытки. Код выделил в отдельный пакет. Создал два класса 1. Selector - класс для выбора лучшего решения и 2. AdSet - для хранения решений. AdSet хранит сам набор рекламы и два поля - общая продолжительность и стоимость показа всех роликов из набора рекламы. Зачем я так сделал ? Я заметил, что часто приходится подсчитывать эти два параметра. Бегать по всему набору роликов и считать сумму. Решил сделать это один раз. Selecotr принимает в конструктор рекламные ролики (из AdvertisementStorage и продолжительность готовки. Там же в конструкторе из полного набора рекламных роликов делает рабочий набор, отсекая ролики с hints = 0 и продолжительностью больше времени приготовления. С этим внутреннем набором класс и работает. Перебор всех возможных комбинаций сделал по "методу рюкзака", просто и надежно, хотя не супер "красиво". Далее каждый из наборов проверяется на продолжительность и общую стоимость (если стоимость меньше предыдущего набора, то в печь.(как здесь посоветовал один мудрый человек :-)) Если проходит заносим в TreeSet. TreeSet создаем с собственным компаратором, согласно условиям задачи. После перебора всез комбинаций вытаскиваем первый объект из TreeSet - это искомый оптимальный набор. Передаем наверх именно как объект AdSet, т.к. значения продолжительности показа и стоимости еще понадобятся в задаче 14.

Если делаете как в задачи с рюкзаком - подумайте как сделать меньше веток рекурсии, иначе будет тайм аут у валидатора

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

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

а надо:

return 1000 * amountPerOneDisplaying/ duration;

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