Svērtā darba plānošana | 2. kopa (izmantojot LIS)
Doti N darbi, kur katrs darbs ir attēlots, sekojot trim tā elementiem.
1. Sākuma laiks
2. Finish Time
3. Saistītā peļņa vai vērtība
Atrodiet darbu maksimālās peļņas apakškopu tā, lai divi apakškopā esošie darbi nepārklātos.
Piemēri:
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 iepriekšējā ziņa, ko apspriedām par svērto darbu plānošanas problēmu. Mēs apspriedām DP risinājumu, kurā pamatā iekļaujam vai izslēdzam pašreizējo darbu. Šajā ierakstā tiek apspriests vēl viens interesants DP risinājums, kurā mēs arī drukājam darbus. Šī problēma ir standarta variants Visilgākā pieaugošā secība (LIS) problēma. Mums ir nepieciešamas nelielas izmaiņas LIS problēmas dinamiskās programmēšanas risinājumā.
Vispirms mums ir jāsakārto darbi atbilstoši sākuma laikam. Lai darbs[0..n-1] ir darbu masīvs pēc šķirošanas. Mēs definējam vektoru L tā, lai L[i] pats par sevi ir vektors, kas saglabā darba [0..i] svērto darba grafiku, kas beidzas ar uzdevumu [i]. Tāpēc indeksam i L[i] var rekursīvi uzrakstīt kā -
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
Piemēram, apsveriet pārus {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}Mēs izvēlamies vektoru ar lielāko peļņu. Šajā gadījumā L[1].
Zemāk ir iepriekš minētās idejas īstenošana -
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 ); } }
Izvade(1 2 50) (2 100 200)
Mēs varam vēl vairāk optimizēt iepriekš minēto DP risinājumu, noņemot funkciju findSum (). Tā vietā mēs varam uzturēt citu vektoru/masīvu, lai saglabātu maksimālās iespējamās peļņas summu līdz darbam i.Laika sarežģītība Dinamiskās programmēšanas risinājums ir O(n 2 ) kur n ir darbu skaits.
Palīgtelpa Programma izmanto O (n 2 ).
