logo

TechCodeview

Mindestzeitaufwand für die Herstellung von m Artikeln

Gegeben N Maschinen, die durch ein ganzzahliges Array dargestellt werden arr[] Wo arr[i] bezeichnet die Zeit (in Sekunden), die von der benötigt wird i-th Maschine zu produzieren eins Artikel. Alle Maschinen funktionieren gleichzeitig und kontinuierlich. Zusätzlich erhalten wir auch eine ganze Zahl M stellt die Gesamtzahl dar Artikel erforderlich . Die Aufgabe besteht darin, die zu ermitteln Mindestzeit benötigt, um genau zu produzieren M Artikel effizient.

Beispiele:  

Eingang: arr[] = [2 4 5] m = 7
Ausgabe: 8
Erläuterung: Die optimale Art zu produzieren 7 Artikel in der Minimum Zeit ist 8 Sekunden. Jede Maschine produziert Artikel mit unterschiedlichen Geschwindigkeiten:



  • Maschine 1 produziert jeden Artikel einen Artikel 2 Sekunden → Erzeugt 8/2 = 4 Artikel in 8 Sekunden.
  • Maschine 2 produziert jeden Artikel einen Artikel 4 Sekunden → Erzeugt 8/4 = 2 Artikel in 8 Sekunden.
  • Maschine 3 produziert jeden Artikel einen Artikel 5 Sekunden → Erzeugt 8/5 = 1 Artikel in 8 Sekunden.

Insgesamt produzierte Artikel 8 Sekunden = 4 + 2 + 1 = 7


Eingang: arr[] = [2 3 5 7] m = 10
Ausgabe: 9
Erläuterung: Die optimale Art zu produzieren 10 Artikel in der Minimum Zeit ist 9 Sekunden. Jede Maschine produziert Artikel mit unterschiedlichen Geschwindigkeiten:

  • Maschine 1 produziert jeweils einen Artikel 2 Sekunden - Produziert 9/2 = 4 Artikel in 9 Sekunden.
  • Maschine 2 produziert jeweils einen Artikel 3 Sekunden - Produziert 9/3 = 3 Artikel in 9 Sekunden.
  • Maschine 3 produziert jeweils einen Artikel 5 Sekunden - Produziert 9/5 = 1 Artikel in 9 Sekunden.
  • Maschine 4 produziert jeweils einen Artikel 7 Sekunden - Produziert 9/7 = 1 Artikel in 9 Sekunden.

Insgesamt produzierte Artikel 9 Sekunden = 4 + 3 + 1 + 1 = 10

Inhaltsverzeichnis

Verwendung der Brute-Force-Methode – O(n*m*min(arr)) Zeit und O(1) Raum

Die Idee ist schrittweise prüfen die minimale Zeit, die für eine exakte Produktion erforderlich ist M Artikel. Wir beginnen mit Zeit = 1 und erhöhen Sie den Wert weiter, bis die Gesamtmenge der von allen Maschinen produzierten Artikel erreicht ist ≥ m . Bei jedem Zeitschritt berechnen wir die Anzahl der Artikel, mit denen jede Maschine produzieren kann Zeit / arr[i] und fasse sie zusammen. Da alle Maschinen funktionieren gleichzeitig Dieser Ansatz stellt sicher, dass wir die kleinste gültige Zeit finden.

C++ 
// C++ program to find minimum time  // required to produce m items using  // Brute Force Approach #include    using namespace std; int minTimeReq(vector<int> &arr int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.size(); i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  } } int main() {  vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; }
Java 
// Java program to find minimum time  // required to produce m items using  // Brute Force Approach import java.util.*; class GfG {  static int minTimeReq(int arr[] int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.length; i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  }  }  public static void main(String[] args) {    int arr[] = {2 4 5};  int m = 7;  System.out.println(minTimeReq(arr m));  } }
Python 
# Python program to find minimum time  # required to produce m items using  # Brute Force Approach def minTimeReq(arr m): # Start checking from time = 1 time = 1 while True: totalItems = 0 # Calculate total items produced at  # current time for i in range(len(arr)): totalItems += time // arr[i] # If we produce at least m items  # return the time if totalItems >= m: return time # Otherwise increment time and  # continue checking time += 1 if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m))
C# 
// C# program to find minimum time  // required to produce m items using  // Brute Force Approach using System; class GfG {  static int minTimeReq(int[] arr int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.Length; i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  }  }  public static void Main() {    int[] arr = {2 4 5};  int m = 7;  Console.WriteLine(minTimeReq(arr m));  } }
JavaScript 
// JavaScript program to find minimum time  // required to produce m items using  // Brute Force Approach function minTimeReq(arr m) {    // Start checking from time = 1  let time = 1;    while (true) {  let totalItems = 0;  // Calculate total items produced at   // current time  for (let i = 0; i < arr.length; i++) {  totalItems += Math.floor(time / arr[i]);  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  } } // Input values let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m));

Ausgabe 
8

Zeitkomplexität: O(n*m*min(arr)) denn für jede Zeiteinheit (bis zu m * min(arr)) durchlaufen wir n Maschinen, um produzierte Artikel zu zählen.
Raumkomplexität: O(1) da nur wenige Integer-Variablen verwendet werden; Es wird kein zusätzlicher Speicherplatz zugewiesen.

Verwenden der binären Suche – O(n*log(m*min(arr))) Zeit und O(1) Raum

Der Idee ist zu verwenden Binäre Suche anstatt jedes Mal nachzuschauen Der Reihe nach Wir beobachten, dass die Gesamtmenge der in einer bestimmten Zeit produzierten Artikel T kann berechnet werden An) . Die wichtigste Beobachtung ist, dass die minimal mögliche Zeit beträgt 1 und die maximal mögliche Zeit ist m * minMachineTime . Durch die Bewerbung Binäre Suche In diesem Bereich überprüfen wir wiederholt den Mittelwert, um festzustellen, ob er ausreicht, und passen den Suchraum entsprechend an.

Schritte zur Umsetzung der oben genannten Idee:

  • Nach links stellen zu 1 und Rechts Zu m * minMachineTime um den Suchraum zu definieren.
  • Ans initialisieren mit Rechts um die minimal erforderliche Zeit zu speichern.
  • Führen Sie eine binäre Suche aus während links kleiner oder gleich ist Rechts .
  • Mitte berechnen und berechnen Sie totalItems durch Iterieren arr und zusammenfassend Mitte / Ar[i] .
  • Wenn totalItems mindestens m ist aktualisieren Jahre Und Suche nach einer kürzeren Zeit. Ansonsten anpassen links Zu Mitte + 1 für eine längere Zeit.
  • Suchen Sie weiter bis die optimale Mindestzeit gefunden ist.
C++ 
// C++ program to find minimum time  // required to produce m items using  // Binary Search Approach #include    using namespace std; int minTimeReq(vector<int> &arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.size(); i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.size(); i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans; } int main() {    vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; }
Java 
// Java program to find minimum time  // required to produce m items using  // Binary Search Approach import java.util.*; class GfG {    static int minTimeReq(int[] arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.length; i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans;  }  public static void main(String[] args) {    int[] arr = {2 4 5};  int m = 7;  System.out.println(minTimeReq(arr m));  } }
Python 
# Python program to find minimum time  # required to produce m items using  # Binary Search Approach def minTimeReq(arr m): # Find the minimum value in arr manually minMachineTime = arr[0] for i in range(1 len(arr)): if arr[i] < minMachineTime: minMachineTime = arr[i] # Define the search space left = 1 right = m * minMachineTime ans = right while left <= right: # Calculate mid time mid = left + (right - left) // 2 totalItems = 0 # Calculate total items produced in 'mid' time for i in range(len(arr)): totalItems += mid // arr[i] # If we can produce at least m items # update answer if totalItems >= m: ans = mid # Search for smaller time right = mid - 1 else: # Search in right half left = mid + 1 return ans if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m))
C# 
// C# program to find minimum time  // required to produce m items using  // Binary Search Approach using System; class GfG {    static int minTimeReq(int[] arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.Length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.Length; i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans;  }  static void Main() {    int[] arr = {2 4 5};  int m = 7;  Console.WriteLine(minTimeReq(arr m));  } }
JavaScript 
// JavaScript program to find minimum time  // required to produce m items using  // Binary Search Approach function minTimeReq(arr m) {    // Find the minimum value in arr manually  let minMachineTime = arr[0];  for (let i = 1; i < arr.length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  let left = 1;  let right = m * minMachineTime;  let ans = right;    while (left <= right) {    // Calculate mid time  let mid = Math.floor(left + (right - left) / 2);  let totalItems = 0;  // Calculate total items produced in 'mid' time  for (let i = 0; i < arr.length; i++) {  totalItems += Math.floor(mid / arr[i]);  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans; } // Driver code let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m));

Ausgabe 
8

Zeitkomplexität: O(n log(m*min(arr))) Da die Binärsuche log(m × min(arr)) mal ausgeführt wird, werden jeweils n Maschinen überprüft.
Raumkomplexität: O(1) da nur wenige zusätzliche Variablen verwendet werden, ist der Raum konstant.
 

Quiz erstellen