Доброго дня! Люди добрые, да и злые тоже :)), подскажите, по принципу "Задача о рюкзаке" как решить эту задачу. Как найти один лучший вариант это понятно, я реализовал. НО!!! А если этих лучших вариантов по стоимости несколько. Тогда как решить по принципу "Задача о рюкзаке"?
Выполнить вот это требование: Если существует несколько вариантов набора видео-роликов с одинаковой суммой денег, полученной от показов, то должен быть выбран вариант с максимальным суммарным временем.
Mikhail
1 уровень
Задача о рюкзаке
Обсуждается
Комментарии (3)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Павел Безумный учёный Expert
5 февраля 2022, 11:41
Подобрать оптимальный список видео можно, если производить сравнение комплексно по всем трём параметрам:
1) общей стоимости показа плейлиста;
2) общему времени воспроизведения плейлиста;
3) количеству роликов в плейлисте.
Алгоритм поиска в общем виде может быть таким: при помощи "жадного" принципа выбираем первый подходящий плейлист, длительность которого не превышает время заказа. Этот найденный плейлист будем считать оптимальным, пока не обнаружены другие плейлисты, могущие составить ему конкуренцию. Сохраняем плейлист во временную переменную (пусть будет bestPlaylist). Ищем следующий подходящий плейлист, то есть со стоимостью показа не меньшей, чем уже имеющийся bestPlaylist. Если вновь составленный список дороже, чем bestPlaylist, то временная переменная перезаписывается этим новым плейлистом, более "оптимальным". Если сравниваемые плейлисты имеют одинаковую стоимость показа, то производится сравнение по второму параметру - общему времени воспроизведения, и выбирается тот, чьё суммарное время больше. Если же окажется, что и время показа у обоих плейлистов одинаковое, то необходимо сравнить списки по третьему параметру, то есть по количеству роликов в каждом плейлисте, и выбрать тот, котором их меньше. Далее переходим к составлению следующего плейлиста, после чего опять сравниваем его с текущим bestPlaylist. После перебора всех возможных комбинаций поле bestPlaylist будет содержать ссылку на оптимальный список видео.
Для ускорения работы алгоритма можно также завести поля bestAmount и bestDuration, содержащие соответственно значения стоимости показа и длительности текущего оптимального плейлиста bestPlaylist, чтобы не пересчитывать эти значения при сравнении списков.
+3
Mikhail
5 февраля 2022, 12:20
Я правильно понимаю, что решить эту задачу по принципу "Задача о рюкзаке" не получится? Кроме как найти один из лучших вариантов.
0
Павел Безумный учёный Expert
5 февраля 2022, 12:58
Почему же? Описанный выше алгоритм как раз является одним из решений задачи о рюкзаке. Пусть изначально в нашем распоряжении имеются 10 видео, условно обозначим их:
Поскольку алгоритм "жадный", то есть пытающийся захватить максимальное значение заданного основного параметра (стоимости показа списка), берём все 10 роликов. Проверяем - оказывается, что список слишком длинный по времени показа. Отбрасываем один ролик. У нас остаётся:
Опять проверяем по общей длительности - и, к примеру, оказывается, что опять не влезает. Отбрасываем ещё один ролик, получаем:
После проверки выясняется, что длительность полученного списка из восьми роликов не превышает время заказа - значит, мы собрали один из вариантов "рюкзака". Дальнейшая обработка оставшихся восьми роликов путём отбрасывания не имеет смысла, поскольку очевидно, что каждая из подмножества полученных комбинаций будет уступать уже имеющейся как по длительности, так и по стоимости показа. Поэтому прерываем эту бесперспективную "ветку" и возвращаемся в предыдущую точку:
Но теперь мы отбрасываем не девятый ролик, а восьмой, и получаем:
и действуем аналогично описанному выше в поисках следующего подходящего "рюкзака".
В процессе работы алгоритм должен пройтись по всему дереву возможных вариантов "рюкзака", что может занять весьма много времени при большом количестве роликов в исходном наборе. Но отбрасывание заведомо неподходящих ветвей дерева позволяет существенно сократить время поиска.
+1