logo

TechCodeview

Минимално време потребно за производњу м артикала

Дато н машине представљене целим низом арр[] где арр[и] означава време (у секундама) које је потребно и-тх машина за производњу један предмет. Све машине раде истовремено и континуирано. Поред тога, такође нам је дат цео број м који представља укупан број потребне ставке . Задатак је да се утврди минимално време потребно за производњу тачно м ставке ефикасно.

Примери:  

Улаз: арр[] = [2 4 5] м = 7
Излаз: 8
Објашњење: Оптималан начин производње 7 ставке у минимум време је 8 секунди. Свака машина производи артикле различитим брзинама:



  • Машина 1 производи сваки предмет 2 секунди → Производи 8/2 = 4 ставке у 8 секунди.
  • Машина 2 производи сваки предмет 4 секунди → Производи 8/4 = 2 ставке у 8 секунди.
  • Машина 3 производи сваки предмет 5 секунди → Производи 8/5 = 1 ставка у 8 секунди.

Укупни производи произведени у 8 секунди = 4 + 2 + 1 = 7


Улаз: арр[] = [2 3 5 7] м = 10
Излаз: 9
Објашњење: Оптималан начин производње 10 ставке у минимум време је 9 секунди. Свака машина производи артикле различитим брзинама:

  • Машина 1 производи сваки предмет 2 секунди - Производи 9/2 = 4 ставке за 9 секунди.
  • Машина 2 производи сваки предмет 3 секунди - Производи 9/3 = 3 ставке за 9 секунди.
  • Машина 3 производи сваки предмет 5 секунди - Производи 9/5 = 1 предмет за 9 секунди.
  • Машина 4 производи сваки предмет 7 секунди - Производи 9/7 = 1 предмет за 9 секунди.

Укупни производи произведени у 9 секунди = 4 + 3 + 1 + 1 = 10

Садржај

Коришћење методе грубе силе – О(н*м*мин(арр)) време и О(1) простор

Идеја је да постепено проверавати минимално време потребно да се тачно произведе м ставке. Почињемо са време = 1 и наставите да га повећавате све док не добијете укупан број артикала које производе све машине ≥ м . У сваком временском кораку израчунавамо број предмета које свака машина може да произведе користећи време / арр[и] и сумирати их. Пошто све машине раде истовремено овај приступ осигурава да пронађемо најмање важеће време.

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));

Излаз 
8

Временска сложеност: О(н*м*мин(арр)) јер за сваку временску јединицу (до м * мин(арр)) понављамо кроз н машина да бисмо пребројали произведене артикле.
Сложеност простора: О(1) пошто се користи само неколико целобројних променљивих; није додељен додатни простор.

Коришћење бинарне претраге - О(н*лог(м*мин(арр))) Време и О(1) простор

Тхе идеја је користити Бинарно претраживање уместо да сваки пут проверава секвенцијално примећујемо да укупни предмети произведени у датом времену Т може се израчунати у О(н) . Кључно запажање је да је минимално могуће време 1 а максимално могуће време је м * минМацхинеТиме . Пријавом бинарно претраживање у овом опсегу више пута проверавамо средњу вредност да бисмо утврдили да ли је довољна и у складу са тим прилагођавамо простор за претрагу.

Кораци за имплементацију горње идеје:

  • Поставите лево до 1 и право да м * минМацхинеТиме да дефинишете простор за претрагу.
  • Иницијализујте анс са право за чување минималног потребног времена.
  • Покрените бинарну претрагу док лево је мање или једнако право .
  • Израчунај средину и израчунајте тоталИтемс итерацијом кроз арр и сумирајући средина / арр[и] .
  • Ако је тоталИтемс најмање м ажурирати године и тражи мање време. У супротном прилагодите лево то средина + 1 за веће време.
  • Наставите да тражите док се не пронађе оптимално минимално време.
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));

Излаз 
8

Временска сложеност: О(н лог(м*мин(арр))) као Бинарна претрага покреће лог(м × мин(арр)) пута сваки провера н машина.
Сложеност простора: О(1) пошто се користи само неколико додатних варијабли што га чини константним простором.
 

Креирај квиз