Almacenamiento óptimo en cintas

Dados  los programas almacenados en una cinta de computadora y la longitud de cada programa  es  donde  , encuentre el orden en el que los programas deben almacenarse en la cinta para el cual  se minimiza el tiempo medio de recuperación (MRT dado como ).
Ejemplo: 
 

Input : n = 3
        L[] = { 5, 3, 10 }
Output : Order should be { 3, 5, 10 } with MRT = 29/3

Prerrequisitos: Almacenamiento de datos en cintas magnéticas 
 

Primero analicemos el problema y comprendamos lo que se debe hacer.
Una cinta magnética solo proporciona acceso secuencial a los datos. En una cinta/cassette de audio, a diferencia de un CD, una quinta canción de la cinta no se puede reproducir directamente. Se debe recorrer la duración de las primeras cuatro canciones para reproducir la quinta canción. Entonces, para acceder a ciertos datos, la cabeza de la cinta debe colocarse en consecuencia.
Ahora supongamos que hay 4 canciones en una cinta de duración de audio de 5, 7, 3 y 2 minutos respectivamente. Para reproducir la cuarta canción, necesitamos atravesar una longitud de audio de 5 + 7 + 3 = 15 minutos y luego colocar el cabezal de la cinta. 
El tiempo de recuperación de los datos es el tiempo necesario para recuperar/acceder a esos datos en su totalidad. Por lo tanto, el tiempo de recuperación de la cuarta canción es 15 + 2 = 17 minutos.
Ahora, considerando que todos los programas en una cinta magnética se recuperan con la misma frecuencia y el cabezal de la cinta apunta hacia el frente de la cinta cada vez, se puede definir un nuevo término llamado Tiempo medio de recuperación (MRT).
Supongamos que el tiempo de recuperación del programa  es  . Por lo tanto, 
MRT es el promedio de todos esos  . Por lo tanto  , o 
El acceso secuencial de datos en una cinta tiene algunas limitaciones. Debe definirse el orden en el que se almacenan los datos/programas en una cinta para que se pueda obtener la menor cantidad de MRT. Por lo tanto, el orden de almacenamiento se vuelve muy importante para reducir el tiempo de acceso/recuperación de datos. 
Por lo tanto, la tarea se reduce: definir el orden correcto y, por lo tanto, minimizar el MRT, es decir, minimizar el término 
Por ejemplo, supongamos que hay 3 programas de longitudes 2, 5 y 4 respectivamente. ¡Así que hay un total de 3! = 6 posibles órdenes de almacenamiento.
 

Está claro que siguiendo el segundo orden en el almacenamiento de los programas, el tiempo medio de recuperación es mínimo.
En el ejemplo anterior, la duración del primer programa se suma ‘n’ veces, la del segundo ‘n-1’ veces… y así sucesivamente hasta que el último programa se agrega solo una vez. Por lo tanto, un análisis cuidadoso sugiere que para minimizar el MRT, los programas que tienen una mayor duración deben colocarse hacia el final para que la suma se reduzca. O bien, la duración de los programas debe clasificarse en orden creciente. Ese es el Algoritmo Greedy en uso: en cada paso, tomamos la decisión inmediata de poner primero el programa que tiene menos tiempo, para construir la solución optimizada final al problema pieza por pieza.
A continuación se muestra la implementación: 
 

// CPP Program to find the order
// of programs for which MRT is
// minimized
#include <bits/stdc++.h>
 
using namespace std;
 
// This functions outputs the required
// order and Minimum Retrieval Time
void findOrderMRT(int L[], int n)
{
    // Here length of i'th program is L[i]
    sort(L, L + n);
 
    // Lengths of programs sorted according to increasing
    // lengths. This is the order in which the programs
    // have to be stored on tape for minimum MRT
    cout << "Optimal order in which programs are to be"
            "stored is: ";
    for (int i = 0; i < n; i++)
        cout << L[i] << " ";
    cout << endl;
 
    // MRT - Minimum Retrieval Time
    double MRT = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j <= i; j++)
            sum += L[j];
        MRT += sum;
    }
    MRT /= n;
    cout << "Minimum Retrieval Time of this"
           " order is " << MRT;
}
 
// Driver Code to test above function
int main()
{
    int L[] = { 2, 5, 4 };
    int n = sizeof(L) / sizeof(L[0]);
    findOrderMRT(L, n);
    return 0;
}

// Java Program to find the order
// of programs for which MRT is
// minimized
import java.io.*;
import java .util.*;
 
class GFG
{
 
// This functions outputs
// the required order and
// Minimum Retrieval Time
static void findOrderMRT(int []L,
                         int n)
{
    // Here length of
    // i'th program is L[i]
    Arrays.sort(L);
 
    // Lengths of programs sorted
    // according to increasing lengths.
    // This is the order in which
    // the programs have to be stored
    // on tape for minimum MRT
    System.out.print("Optimal order in which " +
              "programs are to be stored is: ");
    for (int i = 0; i < n; i++)
        System.out.print(L[i] + " ");
        System.out.println();
 
    // MRT - Minimum Retrieval Time
    double MRT = 0;
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = 0; j <= i; j++)
            sum += L[j];
        MRT += sum;
    }
    MRT /= n;
    System.out.print( "Minimum Retrieval Time" +
                    " of this order is " + MRT);
}
 
// Driver Code
public static void main (String[] args)
{
    int []L = { 2, 5, 4 };
    int n = L.length;
    findOrderMRT(L, n);
}
}
 
// This code is contributed
// by anuj_67.

# Python program to find the order of programs for which MRT is minimized
 
# This function outputs the required order and Minimum Retrieval Time
def findOrderMRT(L, n):
 
        # Here length of i'th program is L[i]
    L.sort()
 
    # Lengths of programs sorted according to increasing lengths.
    # This is the order in which the programs have to be stored on tape for minimum MRT
    print("Optimal order in which programs are to be stored is:", end=" ")
    for i in range(0, n):
        print(L[i], end=" ")
    print()
 
    # MRT - Minimum Retrieval Time
    MRT = 0
    for i in range(0, n):
        sum = 0
        for j in range(0, i+1):
            sum += L[j]
        MRT += sum
 
    MRT /= n
    print("Minimum Retrieval Time of this order is", "{0:.5f}".format(MRT))
 
 
L = [2, 5, 4]
n = len(L)
findOrderMRT(L, n)
 
# This code is contributed by lokesh (lokeshmvs21).

// C# Program to find the
// order of programs for
// which MRT is minimized
using System;
 
class GFG
{
 
// This functions outputs
// the required order and
// Minimum Retrieval Time
static void findOrderMRT(int []L,
                         int n)
{
    // Here length of
    // i'th program is L[i]
    Array.Sort(L);
 
    // Lengths of programs sorted
    // according to increasing lengths.
    // This is the order in which
    // the programs have to be stored
    // on tape for minimum MRT
    Console.Write("Optimal order in " +  
                  "which programs are" +
                  " to be stored is: ");
    for (int i = 0; i < n; i++)
        Console.Write(L[i] + " ");
        Console.WriteLine();
 
    // MRT - Minimum Retrieval Time
    double MRT = 0;
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = 0; j <= i; j++)
            sum += L[j];
        MRT += sum;
    }
    MRT /= n;
    Console.WriteLine("Minimum Retrieval " +
                  "Time of this order is " +
                                       MRT);
}
 
// Driver Code
public static void Main ()
{
    int []L = { 2, 5, 4 };
    int n = L.Length;
    findOrderMRT(L, n);
}
}
 
// This code is contributed
// by anuj_67.

<script>
 
// Javascript Program to find the order
// of programs for which MRT is
// minimized
   
// This functions outputs
// the required order and
// Minimum Retrieval Time
function findOrderMRT(L, n)
{
    // Here length of
    // i'th program is L[i]
    L.sort();
   
    // Lengths of programs sorted
    // according to increasing lengths.
    // This is the order in which
    // the programs have to be stored
    // on tape for minimum MRT
   document.write("Optimal order in which " +
              "programs are to be stored is: ");
    for (let i = 0; i < n; i++)
        document.write(L[i] + " ");
        document.write("<br/>");
   
    // MRT - Minimum Retrieval Time
    let MRT = 0;
    for (let i = 0; i < n; i++)
    {
        let sum = 0;
        for (let j = 0; j <= i; j++)
            sum += L[j];
        MRT += sum;
    }
    MRT /= n;
   document.write( "Minimum Retrieval Time" +
                    " of this order is " + MRT);
}
 
// driver code
 
     let L = [ 2, 5, 4 ];
    let n = L.length;
    findOrderMRT(L, n);
     
</script>

Producción: 
 

Optimal order in which programs are to be stored are: 2 4 5 
Minimum Retrieval Time of this order is 6.33333

La complejidad de tiempo del programa anterior es la complejidad de tiempo para la clasificación, es decir  (ya que std::sort() opera en  ) Si usa la clasificación de burbujas en lugar de std::sort(), tomará 
Puede pensar que la complejidad de tiempo para este código anterior en particular debe deberse a ambos bucles en el cálculo de ‘mrt’, es decir, pero recuerde que intuitivamente, los bucles for utilizados también se pueden codificar de esta manera para evitar dos bucles: 
 

for (int i = 0; i < n; i++)
    MRT += (n - i) * L[i];