我有以下问题，对此我只有一点想法：
考虑磁带存储问题。给定n文件的长度l1,...,ln和访问它们的频率f1,...,fn，其中所有频率的总和为1和0<fi<1。“最优”是指最小化这些文件的平均检索时间。例如，如果有两个文件，每个文件的长度10, 4和频率0.8, 0.2，如果先存储文件1，则平均检索时间为10 x 0.8 + 14 x 0.2 = 10.8。
设计了一个算法来寻找最优的顺序并证明了它的有效性。
我的想法：
更大的频率和更大的长度在前面的顺序，但哪个因素应该给予更高的优先权？
最佳答案
这个问题不需要动态编程这是一个简单的排序问题，有一点扭曲。
找到每个文件的frequency / length。这就得到了文件的每个单位长度的访问频率。按降序排序，因为每个文件都被前一个文件的长度“惩罚”。
证明：
假设顺序是固定的然后，交换任何两个相邻的文件不会影响交换位置以外的任何其他li * fi调用交换中的左一个x，另一个y == x+1。然后，平均检索时间的变化是ly*fx - lx*fy。如果fx/lx < fy/ly，则ly*fx < lx*fy这意味着ly*fx - lx*fy < 0，这意味着平均检索时间减少这意味着我们有优势做这个交换无论何时fx/lx < fy/ly我们都会继续进行这样的交换，并且我们将到达一个不再可能的时刻。这一定是最佳答案。
每当left < right时交换相邻的内容类似于按降序进行气泡排序，因此我们通常可以使用任何排序。