Алгоритм формирования списка

250

07 декабря 2017, 00:21

мне нужно придумать алгоритм, который будет формировать плейлист из треков длительностью 1 час. треки находятся в 2 разных папках. в первой те, что обязательно должны присутсвовать в плейлисте, они короткие, каждый должен повторятся N количество раз. во второй те, что заполняют пространство, не занятое треками из первой группы, это обычные песни разной длины. у меня не выходит равномерно заполнить эти пространства. я просто распределяю треки из первой группы равномерно по времени, а потом пытаюсь подобрать песню из другой папки для заполнения промежутков. может ли кто нибудь подсказать другой подход к этой задаче?

Answer 1

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

Ссылки на задачу о рюкзаке (ранце): https://ru.wikipedia.org/wiki/Задача_о_ранце

И её решение: https://habrahabr.ru/post/222577/