算法 - 当我们有每个文本的长度和频率时，如何找到 n 个文本的最小总阅读时间？

Question

问题听起来像这样，我们得到了 n 个文本，它们将被放在磁带/色带/带子上(真的不知道英语中的等价物是什么，但我想你明白我在说什么)。为了阅读位于位置 k 的文本，我们必须阅读位置 1,2,...,k 的文本。
每个文本都有自己的长度和频率(阅读次数)。现在，我们必须想出一个解决方案，将文本按这样的顺序放置总访问时间最少。总访问时间的计算公式为:

n_
 \  f(Ti)[L(T1)+L(T2)+...+L(Ti)]
 /_    
i=1

Now, that little drawing I did is SUM from 1 to n;

f(T i) is the frequency of T i;

L(T i) is the length of T i;

T i is the text situated at position i;

以下是“伪代码”中的等价物，以防有帮助:

n-number of texts;
Ribbon[n]-array of texts
sum=0, sum2=0;
for(i=0;i<n;i++)
   {sum=0;
   for(j=0;j<=i;j++)
      sum=sum+Ribbon[j].length;
   sum2=sum2+sum*Ribbon[i].frequency;}

现在我尝试了一些策略，比如按升序/降序排列文本，根据长度、频率，甚至长度*频率以及我的其他一些想法，但都没有他们成功了，因为我总是找到一个反例，一个元素顺序的总访问时间比我的程序给我的要少。

Answer 1

如果我们交换两个相邻的元素 x 和 y(其中 x 当前紧接在 y 之前)，请考虑总和的变化。

你会发现区别是f(Tx)L(Ty)-f(Ty)L(Tx)。

例如，如果两个长度相同，则如果我们将较高的频率放在前面，我们会减少总和，而如果频率相同，如果我们将较短的长度放在前面，我们会减少总和。

我们可以通过交换相邻元素来达到任何排列(例如考虑冒泡排序)，因此如果您根据这个比较函数对元素进行排序，您将获得最小和。

注意这个比较函数等价于基于L(Tx)/f(Tx)的排序，即我们希望先做短/高频元素。