我正在实现一个系统，其中内存可以以离线方式分配，即所有分配时间，大小和释放时间都是预先知道的，我只需要找出一个最小化峰值内存使用的静态分配 .
谷歌没有多大帮助;大多数结果都是关于各种系统中使用的动态分配器 . 我听说这个问题是NP-Hard，但没有找到好的参考 . 我只发现内存插入和压缩问题是NP-Hard（http://epubs.siam.org/doi/pdf/10.1137/0213037），但它似乎不等于我的情况 .
那么在多项式时间中是否存在最优算法，或者任何良好的次优算法？时间复杂度不是主要问题，只要它可以在几秒钟内完成多核系统上的数千次分配（可能O（n ^ 4）是可接受的） .
非常感谢！
1 回答
这与Filling bins with an equal size问题相似 . 特别是你可以检查Bin打包问题http://en.wikipedia.org/wiki/Bin_packing_problem和其中提到的近似贪婪算法 .