我正在实现一个可以离线分配内存的系统，即所有分配时间、大小和释放时间都是事先已知的，我只需要找出一个静态分配来最小化峰值内存使用。
Google 帮助不大；大多数结果都是关于各种系统中使用的动态分配器的。听说这个问题是NP-Hard的，但是没有找到好的引用。我只发现内存插入和压缩问题是NP-Hard(http://epubs.siam.org/doi/pdf/10.1137/0213037)，但它似乎不等同于我的情况。
那么有没有多项式时间内的最优算法，或者有什么好的次优算法？时间复杂度不是主要问题，只要它可以在几秒内完成多核系统上的数千次分配(也许 O(n^4) 是可以接受的)。
非常感谢!
最佳答案
这称为离线动态存储分配问题。查看 https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 引用的论文以便对文献进行良好的审查。
关于algorithm - 最优离线内存分配算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29573913/