我正在实现一个系统，其中内存可以以离线方式分配，即所有分配时间，大小和释放时间都是预先知道的，我只需要找出一个最小化峰值内存使用的静态分配。
谷歌没有多大帮助;大多数结果都是关于各种系统中使用的动态分配器。我听说这个问题是NP-Hard，但没有找到好的参考。我只发现内存插入和压缩问题是NP-Hard（http://epubs.siam.org/doi/pdf/10.1137/0213037），但它似乎不等于我的情况。
那么在多项式时间中是否存在最优算法，或者任何良好的次优算法？时间复杂度不是主要问题，只要它可以在几秒钟内完成多核系统上的数千次分配（可能O（n ^ 4）是可接受的）。
非常感谢！
这与Filling bins with an equal size问题相似。特别是你可以检查Bin填充问题http://en.wikipedia.org/wiki/Bin_packing_problem和其中提到的近似贪婪算法。
它接近于编译器解决的寄存器分配问题。您可以将寄存器分配建模为图形着色问题（NP完成）。但是，对于寄存器分配，它更简单，因为所有寄存器都相同。对于内存分配，如果你想要一个特定大小的内存块，那么内存需要是连续的。
通过稍微调整图形着色问题（颜色变成数字，加上关于序列号的约束），您可以重新构建问题。我相信它应该仍然是NP完整的。
对于良好的多项式时间算法，我会受到寄存器分配算法的启发。