Planification pondérée des tâches | Ensemble 2 (en utilisant LIS)
Étant donné N emplois où chaque emploi est représenté en suivant trois éléments.
1. Heure de début
2. Heure de fin
3. Bénéfice ou valeur associée
Trouvez le sous-ensemble d’emplois à profit maximum de telle sorte qu’aucun emploi du sous-ensemble ne se chevauche.
Exemples :
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.Dans précédent article dont nous avons discuté sur le problème de planification pondérée des tâches. Nous avons discuté d'une solution DP dans laquelle nous incluons ou excluons essentiellement le travail actuel. Dans cet article, une autre solution DP intéressante est discutée, dans laquelle nous imprimons également les travaux. Ce problème est une variante du standard Sous-séquence croissante la plus longue (LIS) problème. Nous avons besoin d'un léger changement dans la solution de programmation dynamique du problème LIS.
Nous devons d’abord trier les tâches en fonction de l’heure de début. Soit job[0..n-1] le tableau de tâches après le tri. Nous définissons le vecteur L tel que L[i] est lui-même un vecteur qui stocke la planification pondérée des tâches de job[0..i] qui se termine par job[i]. Par conséquent, pour un index i L[i] peut être écrit récursivement sous la forme -
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
Par exemple, considérons les paires {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}Nous choisissons le vecteur avec le profit le plus élevé. Dans ce cas L[1].
Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus –
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 ); } }
Sortir(1 2 50) (2 100 200)
Nous pouvons optimiser davantage la solution DP ci-dessus en supprimant la fonction findSum(). Au lieu de cela, nous pouvons maintenir un autre vecteur/tableau pour stocker la somme du profit maximum possible jusqu'au travail i.Complexité temporelle de la solution de programmation dynamique ci-dessus est O (n 2 ) où n est le nombre de tâches.
Espace auxiliaire utilisé par le programme est O(n 2 ).
