Viktad jobbplanering | Set 2 (med LIS)
Givet N jobb där varje jobb representeras genom att följa tre delar av det.
1. Starttid
2. Sluttid
3. Vinst eller värdeassocierat
Hitta den maximala vinstundermängden av jobb så att inga två jobb i undermängden överlappar varandra.
Exempel:
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.I tidigare inlägg vi har diskuterat om viktat jobbplaneringsproblem. Vi diskuterade en DP-lösning där vi i princip inkluderar eller utesluter nuvarande jobb. I det här inlägget diskuteras en annan intressant DP-lösning där vi även skriver ut Jobben. Detta problem är en variant av standarden Longest Increasing Subsequence (LIS) problem. Vi behöver en liten förändring i den dynamiska programmeringslösningen för LIS-problemet.
Vi behöver först sortera jobb efter starttid. Låt jobb[0..n-1] vara samlingen av jobb efter sortering. Vi definierar vektor L så att L[i] själv är en vektor som lagrar viktad jobbschemaläggning av jobb[0..i] som slutar med jobb[i]. Därför för ett index kan i L[i] skrivas rekursivt som -
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
Tänk till exempel på par {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}Vi väljer vektorn med högst vinst. I detta fall L[1].
Nedan är implementeringen av ovanstående idé –
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 ); } }
Produktion(1 2 50) (2 100 200)
Vi kan ytterligare optimera ovanstående DP-lösning genom att ta bort findSum()-funktionen. Istället kan vi behålla en annan vektor/array för att lagra summan av maximal vinst som är möjlig till jobb i.Tidskomplexitet av ovanstående dynamisk programmeringslösning är O(n 2 ) där n är antalet jobb.
Hjälputrymme som används av programmet är O(n 2 ).
