Вам дан массив длины . Каждый элемент массива принадлежит одному из K классов. Вы должны переставить массив, используя минимальное количество операций подкачки, чтобы все элементы одного и того же класса всегда были сгруппированы вместе, то есть они образуют непрерывный подмассив.
Например:
Осталось еще три действительных соглашения.
Как эта проблема называется в литературе? Есть ли эффективный алгоритм для этого?
terminology
reference-request
sorting
arrays
Марко Букал
источник
источник
Ответы:
Примечание: это доказательство твердости, и я думаю, что существуют практические алгоритмы, такие как целочисленное программирование и т. Д.
Учитывая экземпляр BIN_PACKING , где вы хотите , чтобы упаковать число п 1 , ... , п K в L бункеров размером м 1 , ... , м L , и гарантируется , что Σ п я = Е м J = N , то мы могли бы разработать пример вашей проблемы следующим образом:К N1, … , НК L m1,…,mL ∑ni=∑mj=N
источник
Я также подозреваю, что это NP-сложный, но в отсутствие идеи для доказательства, вот пара быстро вычисляемых нижних границ, которые могут быть полезны для проверки оптимальности эвристического решения или сокращения поиска по ветвям и границам. ,
В вашем примере обе эти оценки дают 1 (в последнем случае можно округлить 0,5), что, конечно, является свободным.
источник