נָתוּן נ מכונות המיוצגות על ידי מערך שלמים arr[] אֵיפֹה arr[i] מציין את הזמן (בשניות) שלקח את i-th מכונה לייצור אֶחָד פָּרִיט. כל המכונות עובדות בּוֹ זְמַנִית וברציפות. בנוסף ניתן לנו גם מספר שלם מ המייצג את המספר הכולל של פריטים נדרשים . המשימה היא לקבוע את זמן מינימום צריך לייצר בדיוק מ פריטים ביעילות.
דוגמאות:
קֶלֶט: arr[] = [2 4 5] m = 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
קֶלֶט: arr[] = [2 3 5 7] m = 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
תוכן עניינים
- שימוש בשיטת כוח גס - O(n*m*min(arr)) זמן ו-O(1) מרחב
- שימוש בחיפוש בינארי - O(n*log(m*min(arr))) זמן ו-O(1) מרחב
שימוש בשיטת כוח גס - O(n*m*min(arr)) זמן ו-O(1) מרחב
C++הרעיון הוא לבדוק בהדרגה הזמן המינימלי הנדרש לייצור מדויק מ פריטים. אנחנו מתחילים עם זמן = 1 והמשך להגדיל אותו עד לסך כל הפריטים המיוצרים על ידי כל המכונות ≥ מ . בכל שלב זמן אנו מחשבים את מספר הפריטים שכל מכונה יכולה לייצר באמצעותה זמן / arr[i] ולסכם אותם. מאז כל המכונות עובדות בּוֹ זְמַנִית גישה זו מבטיחה שנמצא את הזמן התקף הקטן ביותר.
// 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
מורכבות זמן: O(n*m*min(arr)) כי עבור כל יחידת זמן (עד m * min(arr)) אנחנו חוזרים דרך n מכונות כדי לספור פריטים שיוצרו.
מורכבות החלל: O(1) מכיוון שמשתמשים רק בכמה משתנים שלמים; לא מוקצה מקום נוסף.
שימוש בחיפוש בינארי - O(n*log(m*min(arr))) זמן ו-O(1) מרחב
ה רַעְיוֹן הוא להשתמש חיפוש בינארי במקום לבדוק כל פעם ברצף אנו רואים שסך כל הפריטים שיוצרו בזמן נתון ט ניתן לחשב ב עַל) . התצפית המרכזית היא שהזמן המינימלי האפשרי הוא 1 והזמן המקסימלי האפשרי הוא m * minMachineTime . על ידי הגשת מועמדות חיפוש בינארי בטווח זה אנו בודקים שוב ושוב את ערך האמצע כדי לקבוע אם הוא מספיק ולהתאים את מרחב החיפוש בהתאם.
שלבים ליישום הרעיון לעיל:
- קבע שמאלה ל-1 ו יָמִינָה אֶל m * minMachineTime כדי להגדיר את מרחב החיפוש.
- אתחול ans עִם יָמִינָה לאחסן את הזמן המינימלי הנדרש.
- הפעל חיפוש בינארי בְּעוֹד שְׁמֹאל קטן או שווה ל יָמִינָה .
- חשב באמצע ולחשב totalItems על ידי איטרציה דרך arr ומסכם mid / arr[i] .
- אם totalItems הוא לפחות m לְעַדְכֵּן שנים ו לחפש זמן קטן יותר. אחרת התאם שְׁמֹאל אֶל אמצע + 1 לזמן גדול יותר.
- המשך בחיפוש עד שנמצא זמן המינימום האופטימלי.
// 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
מורכבות זמן: O(n log(m*min(arr))) כמו חיפוש בינארי מפעיל log(m × min(arr)) פעמים כל בדיקה של n מכונות.
מורכבות החלל: O(1) מכיוון שרק כמה משתנים נוספים משמשים מה שהופך אותו למרחב קבוע.