Алгоритм наилучшего соответствия
Меня попросили сделать алгоритм, который бы наилучшим образом подходил для некоторой музыки в минимальном количестве папок.
Папки имеют фиксированный размер (например, папки могут содержать только 100 минут музыки).
например: у меня есть музыка с этими длинами ( 50 - 30 -20 - 20 -80 - 70 -15 - 15), и размер папки составляет 100 минут.
Результатом должно быть 3 папки.
Я даже не знаю, как работает алгоритм. есть идеи?!
1 ответ
Похоже, проблема упаковки бункера, которая NP-hard Проблема. Так что вам нужно попробовать каждую возможную комбинацию, пока сумма определенной комбинации не превысит целевое число, вы можете прекратить вычислять эту ветвь и перейти к следующей ветке.
Теперь вы можете оптимизировать свой результат и подсчитать минимальное количество комбинаций, сумма которых равна 100 или любому целевому числу, и этот минимум даст вам количество папок, необходимое для хранения данных. Надеюсь, это поможет.