算法 - 如何将 n 个文本放置在 p 波段上，以使全局访问时间最短。每个文本都有自己的长度

Question

问题听起来像这样，我们得到了 n 个文本，它们将被放置在 p 个磁带/乐队上(真的不知道英语中的等价物是什么，但我想你明白我在说什么谈论)。

为了阅读位于其中一个波段上位置 k 的文本，我们必须从特定波段上的位置 1,2,...,k 读取文本。每个文本都有自己的长度。

现在，我们必须找出一种将文本放置在 p 波段上的方法，以便我们获得最小的全局访问时间。全局访问时间是通过将每个波段的所有总访问时间相加得到的。

一个波段的总访问时间计算公式为:

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

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

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

T i is the text situated at position i on the respective band;

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

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

这里有一个例子来阐明这个问题:

say p is 3, so we get 3 bands
say n is 9, so we get 9 texts and the lengths are : 2, 3, 4, 5, 6, 7,   8,  9, 10 
and they are placed on the bands in the following way:

band-1: 2, 5, 8 -> total accesing time of band-1: 24

band-2: 3, 6, 9 -> total accesing time of band-2: 30

band-3: 4, 7, 10 -> total accesing time of band-3: 36

the global accesing time: 24 + 30 + 36 = 90

Answer 1

我将文本位置称为磁带中特定文本之后出现的文本数量，它也表示文本将被读取多少次。

由于您只对访问时间的总和感兴趣，因此文本如何分组到磁带中没有实际意义，但每个文本的位置是什么，例如在相同位置但在不同磁带上切换 2 个文本不会' t 更改全局访问时间。 虽然在不同位置切换 2 个不同大小的文本会改变时间，但通常较长的文本应放在较低的位置(靠近末尾)

该算法可以是贪婪的，从最长到最短的顺序遍历文本，并将每个文本放在文本最少的磁带之一的最后一个可用位置，例如，如果有 10 个文本和 5 个文本然后较长的 5 个文本将在每个磁带的末尾，而较短的 5 个文本将在其开头。