Gewogen taakplanning | Set 2 (LIS gebruiken)
Gegeven N banen waarbij elke baan wordt weergegeven door drie elementen ervan te volgen.
1. Begintijd
2. Eindtijd
3. Winst of waarde verbonden
Zoek de maximale winstsubset van banen, zodat geen twee banen in de subset elkaar overlappen.
Voorbeelden:
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.In vorig post die we hebben besproken over het probleem van de gewogen taakplanning. We bespraken een DP-oplossing waarbij we in principe de huidige baan wel of niet opnemen. In dit bericht wordt een andere interessante DP-oplossing besproken waarbij we ook de Jobs afdrukken. Dit probleem is een variatie op de standaard Langst stijgende vervolgreeks (LIS) probleem. We hebben een kleine verandering nodig in de dynamische programmeeroplossing van het LIS-probleem.
We moeten eerst de taken sorteren op starttijd. Laat job[0..n-1] de reeks taken zijn na het sorteren. We definiëren vector L zo dat L[i] zelf een vector is die de gewogen taakplanning van job[0..i] opslaat die eindigt met job[i]. Daarom kan L[i] voor een index i L[i] recursief worden geschreven als -
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
Beschouw bijvoorbeeld paren {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}We kiezen de vector met de hoogste winst. In dit geval L[1].
Hieronder vindt u de implementatie van het bovenstaande idee –
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 ); } }
Uitvoer(1 2 50) (2 100 200)
We kunnen de bovenstaande DP-oplossing verder optimaliseren door de functie findSum() te verwijderen. In plaats daarvan kunnen we een andere vector/array behouden om de som van de maximaal mogelijke winst op te slaan tot taak i.Tijdcomplexiteit van bovenstaande dynamische programmeeroplossing is O (n 2 ) waarbij n het aantal banen is.
Hulpruimte gebruikt door het programma is O(n 2 ).
