У меня есть массив фиксированного размера N и три возможные операции ALLOC(numBytes) и FREE(block), которые выделяют и освобождают смежные блоки (интервалы) памяти в данном массиве (аналогично malloc () и free ()) и операция COMPACT, которая уплотняет выделенные блоки (переупорядочивает блоки в массиве, начиная со смещения 0, так что между блоками нет промежутка).
Существует предопределенный список ALLOC и FREE операции, которые должны выполняться последовательно в массиве (порядок не может быть изменен).Проблема заключается в том, что массив может стать очень фрагментированным, и ALLOC завершится сбоем, и каждый раз, когда это происходит, должна выполняться операция COMPACT.
Мне нужен способ выполнения списка операций (для каждой операции ALLOC, чтобы найти лучшее смещение в массиве), чтобы количество необходимых операций COMPACT было минимальным.Обратите внимание, что оптимизация для пикового использования памяти на данный момент не важна.
Есть какие-нибудь указания на то, как эта проблема может быть решена?Я чувствую, что это может быть NP-сложная проблема, но я не могу понять, что это такое.