جدولة الوظائف المرجحة | المجموعة 2 (باستخدام LIS)
إعطاء وظائف N حيث يتم تمثيل كل وظيفة باتباع ثلاثة عناصر منها.
1. وقت البدء
2. وقت الانتهاء
3. الربح أو القيمة المرتبطة
ابحث عن أقصى مجموعة فرعية للربح من الوظائف بحيث لا تتداخل وظيفتان في المجموعة الفرعية.
أمثلة:
Input:
Number of Jobs n = 4
Job Details {Start Time Finish Time Profit}
Job 1: {1 2 50}
Job 2: {3 5 20}
Job 3: {6 19 100}
Job 4: {2 100 200}
Output:
Job 1: {1 2 50}
Job 4: {2 100 200}
Explanation: We can get the maximum profit by
scheduling jobs 1 and 4 and maximum profit is 250.في سابق منشور ناقشناه حول مشكلة جدولة الوظائف المرجحة. لقد ناقشنا حل DP حيث نقوم بشكل أساسي بتضمين أو استبعاد الوظيفة الحالية. في هذا المنشور تتم مناقشة حل DP آخر مثير للاهتمام حيث نقوم أيضًا بطباعة المهام. هذه المشكلة هي اختلاف المعيار أطول تسلسل لاحق متزايد (LIS) مشكلة. نحن بحاجة إلى تغيير بسيط في حل البرمجة الديناميكية لمشكلة LIS.
نحتاج أولاً إلى فرز الوظائف وفقًا لوقت البدء. دع job[0..n-1] يكون مجموعة الوظائف بعد الفرز. نحن نحدد المتجه L بحيث يكون L[i] في حد ذاته ناقلًا يخزن جدولة الوظائف المرجحة للوظيفة[0..i] التي تنتهي بالوظيفة[i]. لذلك بالنسبة للفهرس i يمكن كتابة L[i] بشكل متكرر كـ -
L[0] = {job[0]}
L[i] = {MaxSum(L[j])} + job[i] where j < i and job[j].finish <= job[i].start
= job[i] if there is no such j
على سبيل المثال، فكر في أزواج {3 10 20} {1 2 50} {6 19 100} {2 100 200}After sorting we get
{1 2 50} {2 100 200} {3 10 20} {6 19 100}
Therefore
L[0]: {1 2 50}
L[1]: {1 2 50} {2 100 200}
L[2]: {1 2 50} {3 10 20}
L[3]: {1 2 50} {6 19 100}نختار المتجه الذي يحقق أعلى ربح. في هذه الحالة ل[1].
وفيما يلي تنفيذ الفكرة المذكورة أعلاه -
C++Java// C++ program for weighted job scheduling using LIS #include#include #include using namespace std ; // A job has start time finish time and profit. struct Job { int start finish profit ; }; // Utility function to calculate sum of all vector // elements int findSum ( vector < Job > arr ) { int sum = 0 ; for ( int i = 0 ; i < arr . size (); i ++ ) sum += arr [ i ]. profit ; return sum ; } // comparator function for sort function int compare ( Job x Job y ) { return x . start < y . start ; } // The main function that finds the maximum possible // profit from given array of jobs void findMaxProfit ( vector < Job > & arr ) { // Sort arr[] by start time. sort ( arr . begin () arr . end () compare ); // L[i] stores Weighted Job Scheduling of // job[0..i] that ends with job[i] vector < vector < Job >> L ( arr . size ()); // L[0] is equal to arr[0] L [ 0 ]. push_back ( arr [ 0 ]); // start from index 1 for ( int i = 1 ; i < arr . size (); i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {MaxSum(L[j])} + arr[i] where j < i // and arr[j].finish <= arr[i].start if (( arr [ j ]. finish <= arr [ i ]. start ) && ( findSum ( L [ j ]) > findSum ( L [ i ]))) L [ i ] = L [ j ]; } L [ i ]. push_back ( arr [ i ]); } vector < Job > maxChain ; // find one with max profit for ( int i = 0 ; i < L . size (); i ++ ) if ( findSum ( L [ i ]) > findSum ( maxChain )) maxChain = L [ i ]; for ( int i = 0 ; i < maxChain . size (); i ++ ) cout < < '(' < < maxChain [ i ]. start < < ' ' < < maxChain [ i ]. finish < < ' ' < < maxChain [ i ]. profit < < ') ' ; } // Driver Function int main () { Job a [] = { { 3 10 20 } { 1 2 50 } { 6 19 100 } { 2 100 200 } }; int n = sizeof ( a ) / sizeof ( a [ 0 ]); vector < Job > arr ( a a + n ); findMaxProfit ( arr ); return 0 ; } Python// Java program for weighted job // scheduling using LIS import java.util.ArrayList ; import java.util.Arrays ; import java.util.Collections ; import java.util.Comparator ; class Graph { // A job has start time finish time // and profit. static class Job { int start finish profit ; public Job ( int start int finish int profit ) { this . start = start ; this . finish = finish ; this . profit = profit ; } }; // Utility function to calculate sum of all // ArrayList elements static int findSum ( ArrayList < Job > arr ) { int sum = 0 ; for ( int i = 0 ; i < arr . size (); i ++ ) sum += arr . get ( i ). profit ; return sum ; } // The main function that finds the maximum // possible profit from given array of jobs static void findMaxProfit ( ArrayList < Job > arr ) { // Sort arr[] by start time. Collections . sort ( arr new Comparator < Job > () { @Override public int compare ( Job x Job y ) { return x . start - y . start ; } }); // sort(arr.begin() arr.end() compare); // L[i] stores Weighted Job Scheduling of // job[0..i] that ends with job[i] ArrayList < ArrayList < Job >> L = new ArrayList <> (); for ( int i = 0 ; i < arr . size (); i ++ ) { L . add ( new ArrayList <> ()); } // L[0] is equal to arr[0] L . get ( 0 ). add ( arr . get ( 0 )); // Start from index 1 for ( int i = 1 ; i < arr . size (); i ++ ) { // For every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {MaxSum(L[j])} + arr[i] where j < i // and arr[j].finish <= arr[i].start if (( arr . get ( j ). finish <= arr . get ( i ). start ) && ( findSum ( L . get ( j )) > findSum ( L . get ( i )))) { ArrayList < Job > copied = new ArrayList <> ( L . get ( j )); L . set ( i copied ); } } L . get ( i ). add ( arr . get ( i )); } ArrayList < Job > maxChain = new ArrayList <> (); // Find one with max profit for ( int i = 0 ; i < L . size (); i ++ ) if ( findSum ( L . get ( i )) > findSum ( maxChain )) maxChain = L . get ( i ); for ( int i = 0 ; i < maxChain . size (); i ++ ) { System . out . printf ( '(%d %d %d)n' maxChain . get ( i ). start maxChain . get ( i ). finish maxChain . get ( i ). profit ); } } // Driver code public static void main ( String [] args ) { Job [] a = { new Job ( 3 10 20 ) new Job ( 1 2 50 ) new Job ( 6 19 100 ) new Job ( 2 100 200 ) }; ArrayList < Job > arr = new ArrayList <> ( Arrays . asList ( a )); findMaxProfit ( arr ); } } // This code is contributed by sanjeev2552C## Python program for weighted job scheduling using LIS import sys # A job has start time finish time and profit. class Job : def __init__ ( self start finish profit ): self . start = start self . finish = finish self . profit = profit # Utility function to calculate sum of all vector elements def findSum ( arr ): sum = 0 for i in range ( len ( arr )): sum += arr [ i ] . profit return sum # comparator function for sort function def compare ( x y ): if x . start < y . start : return - 1 elif x . start == y . start : return 0 else : return 1 # The main function that finds the maximum possible profit from given array of jobs def findMaxProfit ( arr ): # Sort arr[] by start time. arr . sort ( key = lambda x : x . start ) # L[i] stores Weighted Job Scheduling of job[0..i] that ends with job[i] L = [[] for _ in range ( len ( arr ))] # L[0] is equal to arr[0] L [ 0 ] . append ( arr [ 0 ]) # start from index 1 for i in range ( 1 len ( arr )): # for every j less than i for j in range ( i ): # L[i] = {MaxSum(L[j])} + arr[i] where j < i # and arr[j].finish <= arr[i].start if arr [ j ] . finish <= arr [ i ] . start and findSum ( L [ j ]) > findSum ( L [ i ]): L [ i ] = L [ j ][:] L [ i ] . append ( arr [ i ]) maxChain = [] # find one with max profit for i in range ( len ( L )): if findSum ( L [ i ]) > findSum ( maxChain ): maxChain = L [ i ] for i in range ( len ( maxChain )): print ( '( {} {} {} )' . format ( maxChain [ i ] . start maxChain [ i ] . finish maxChain [ i ] . profit ) end = ' ' ) # Driver Function if __name__ == '__main__' : a = [ Job ( 3 10 20 ) Job ( 1 2 50 ) Job ( 6 19 100 ) Job ( 2 100 200 )] findMaxProfit ( a )JavaScriptusing System ; using System.Collections.Generic ; using System.Linq ; public class Graph { // A job has start time finish time // and profit. public class Job { public int start finish profit ; public Job ( int start int finish int profit ) { this . start = start ; this . finish = finish ; this . profit = profit ; } }; // Utility function to calculate sum of all // ArrayList elements public static int FindSum ( List < Job > arr ) { int sum = 0 ; for ( int i = 0 ; i < arr . Count ; i ++ ) sum += arr . ElementAt ( i ). profit ; return sum ; } // The main function that finds the maximum // possible profit from given array of jobs public static void FindMaxProfit ( List < Job > arr ) { // Sort arr[] by start time. arr . Sort (( x y ) => x . start . CompareTo ( y . start )); // L[i] stores Weighted Job Scheduling of // job[0..i] that ends with job[i] List < List < Job >> L = new List < List < Job >> (); for ( int i = 0 ; i < arr . Count ; i ++ ) { L . Add ( new List < Job > ()); } // L[0] is equal to arr[0] L [ 0 ]. Add ( arr [ 0 ]); // Start from index 1 for ( int i = 1 ; i < arr . Count ; i ++ ) { // For every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {MaxSum(L[j])} + arr[i] where j < i // and arr[j].finish <= arr[i].start if (( arr [ j ]. finish <= arr [ i ]. start ) && ( FindSum ( L [ j ]) > FindSum ( L [ i ]))) { List < Job > copied = new List < Job > ( L [ j ]); L [ i ] = copied ; } } L [ i ]. Add ( arr [ i ]); } List < Job > maxChain = new List < Job > (); // Find one with max profit for ( int i = 0 ; i < L . Count ; i ++ ) if ( FindSum ( L [ i ]) > FindSum ( maxChain )) maxChain = L [ i ]; for ( int i = 0 ; i < maxChain . Count ; i ++ ) { Console . WriteLine ( '({0} {1} {2})' maxChain [ i ]. start maxChain [ i ]. finish maxChain [ i ]. profit ); } } // Driver code public static void Main ( String [] args ) { Job [] a = { new Job ( 3 10 20 ) new Job ( 1 2 50 ) new Job ( 6 19 100 ) new Job ( 2 100 200 ) }; List < Job > arr = new List < Job > ( a ); FindMaxProfit ( arr ); } }
الإخراج(1 2 50) (2 100 200)
يمكننا تحسين حل DP أعلاه عن طريق إزالة وظيفة findSum(). بدلاً من ذلك، يمكننا الاحتفاظ بمتجه/مصفوفة أخرى لتخزين أقصى قدر ممكن من الربح حتى المهمة i.تعقيد الوقت من حل البرمجة الديناميكية أعلاه هو O(n 2 ) حيث n هو عدد الوظائف.
مساحة مساعدة المستخدم في البرنامج هو O(n 2 ).
