Finden Sie Jobs, die an der gewichteten Jobplanung beteiligt sind
Gegeben sind N Jobs, bei denen jeder Job durch die folgenden drei Elemente repräsentiert wird.
1. Startzeit
2. Endzeit
3. Mit Gewinn oder Wert verbunden
Finden Sie die Teilmenge der Jobs mit maximalem Gewinn verbunden, so dass sich keine zwei Jobs in der Teilmenge überschneiden.
Beispiele:
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: Jobs involved in maximum profit are Job 1: {1 2 50} Job 4: {2 100 200} In vorherige Beitrag, den wir über das Problem der gewichteten Jobplanung besprochen haben. Der Beitrag behandelte jedoch nur Code, der sich auf die Erzielung des maximalen Gewinns bezieht. In diesem Beitrag drucken wir auch die Jobs ab, die mit maximalem Gewinn verbunden sind.
Sei arr[0..n-1] das Eingabearray von Jobs. Wir definieren ein Array DP[], sodass DP[i] die beteiligten Jobs speichert, um den maximalen Gewinn des Arrays arr[0..i] zu erzielen. d. h. DP[i] speichert die Lösung für das Teilproblem arr[0..i]. Der Rest des Algorithmus bleibt derselbe wie in beschrieben vorherige Post.
Unten ist die C++-Implementierung:
CPP // C++ program for weighted job scheduling using Dynamic // Programming and Binary Search #include using namespace std ; // A job has start time finish time and profit. struct Job { int start finish profit ; }; // to store subset of jobs struct weightedJob { // vector of Jobs vector < Job > job ; // find profit associated with included Jobs int value ; }; // A utility function that is used for sorting events // according to finish time bool jobComparator ( Job s1 Job s2 ) { return ( s1 . finish < s2 . finish ); } // A Binary Search based function to find the latest job // (before current job) that doesn't conflict with current // job. 'index' is index of the current job. This function // returns -1 if all jobs before index conflict with it. The // array jobs[] is sorted in increasing order of finish time int latestNonConflict ( Job jobs [] int index ) { // Initialize 'lo' and 'hi' for Binary Search int lo = 0 hi = index - 1 ; // Perform binary Search iteratively while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( jobs [ mid ]. finish <= jobs [ index ]. start ) { if ( jobs [ mid + 1 ]. finish <= jobs [ index ]. start ) lo = mid + 1 ; else return mid ; } else hi = mid - 1 ; } return -1 ; } // The main function that finds the subset of jobs // associated with maximum profit such that no two // jobs in the subset overlap. int findMaxProfit ( Job arr [] int n ) { // Sort jobs according to finish time sort ( arr arr + n jobComparator ); // Create an array to store solutions of subproblems. // DP[i] stores the Jobs involved and their total profit // till arr[i] (including arr[i]) weightedJob DP [ n ]; // initialize DP[0] to arr[0] DP [ 0 ]. value = arr [ 0 ]. profit ; DP [ 0 ]. job . push_back ( arr [ 0 ]); // Fill entries in DP[] using recursive property for ( int i = 1 ; i < n ; i ++ ) { // Find profit including the current job int inclProf = arr [ i ]. profit ; int l = latestNonConflict ( arr i ); if ( l != - 1 ) inclProf += DP [ l ]. value ; // Store maximum of including and excluding if ( inclProf > DP [ i - 1 ]. value ) { DP [ i ]. value = inclProf ; // including previous jobs and current job DP [ i ]. job = DP [ l ]. job ; DP [ i ]. job . push_back ( arr [ i ]); } else // excluding the current job DP [ i ] = DP [ i - 1 ]; } // DP[n - 1] stores the result cout < < 'Optimal Jobs for maximum profits are n ' ; for ( int i = 0 ; i < DP [ n -1 ]. job . size (); i ++ ) { Job j = DP [ n -1 ]. job [ i ]; cout < < '(' < < j . start < < ' ' < < j . finish < < ' ' < < j . profit < < ')' < < endl ; } cout < < ' n Total Optimal profit is ' < < DP [ n - 1 ]. value ; } // Driver program int main () { Job arr [] = {{ 3 5 20 } { 1 2 50 } { 6 19 100 } { 2 100 200 } }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); findMaxProfit ( arr n ); return 0 ; }
Java // Java program for weighted job scheduling using Dynamic // Programming and Binary Search import java.util.* ; public class WeightedJobScheduling { // 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 ; } } // to store subset of jobs static class weightedJob { // vector of Jobs List < Job > job ; // find profit associated with included Jobs int value ; public weightedJob () { job = new ArrayList <> (); } } // A utility function that is used for sorting events // according to finish time static class JobComparator implements Comparator < Job > { @Override public int compare ( Job j1 Job j2 ) { return j1 . finish - j2 . finish ; } } // A Binary Search based function to find the latest job // (before current job) that doesn't conflict with current // job. 'index' is index of the current job. This function // returns -1 if all jobs before index conflict with it. The // array jobs[] is sorted in increasing order of finish time static int latestNonConflict ( Job [] jobs int index ) { // Initialize 'lo' and 'hi' for Binary Search int lo = 0 hi = index - 1 ; // Perform binary Search iteratively while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( jobs [ mid ] . finish <= jobs [ index ] . start ) { if ( jobs [ mid + 1 ] . finish <= jobs [ index ] . start ) { lo = mid + 1 ; } else { return mid ; } } else { hi = mid - 1 ; } } return - 1 ; } // The main function that finds the subset of jobs // associated with maximum profit such that no two // jobs in the subset overlap. static int findMaxProfit ( Job [] arr ) { // Sort jobs according to finish time Arrays . sort ( arr new JobComparator ()); // Create an array to store solutions of subproblems. // DP[i] stores the Jobs involved and their total profit // till arr[i] (including arr[i]) weightedJob [] DP = new weightedJob [ arr . length ] ; DP [ 0 ] = new weightedJob (); // initialize DP[0] to arr[0] DP [ 0 ] . value = arr [ 0 ] . profit ; DP [ 0 ] . job . add ( arr [ 0 ] ); // Fill entries in DP[] using recursive property for ( int i = 1 ; i < arr . length ; i ++ ) { // Find profit including the current job int inclProf = arr [ i ] . profit ; int l = latestNonConflict ( arr i ); if ( l != - 1 ) { inclProf += DP [ l ] . value ; } // Store maximum of including and excluding if ( inclProf > DP [ i - 1 ] . value ) { DP [ i ] = new weightedJob (); DP [ i ] . value = inclProf ; DP [ i ] . job . addAll ( DP [ l ] . job ); DP [ i ] . job . add ( arr [ i ] ); } else { DP [ i ] = DP [ i - 1 ] ; } } // DP[n - 1] stores the result System . out . println ( 'Optimal Jobs for maximum profits are' ); for ( Job j : DP [ arr . length - 1 ] . job ) { System . out . println ( '(' + j . start + ' ' + j . finish + ' ' + j . profit + ')' ); } System . out . println ( 'nTotal Optimal profit is ' + DP [ arr . length - 1 ] . value ); return DP [ arr . length - 1 ] . value ; } // Driver program public static void main ( String [] args ) { Job [] arr = { new Job ( 3 5 20 ) new Job ( 1 2 50 ) new Job ( 6 19 100 ) new Job ( 2 100 200 ) }; findMaxProfit ( arr ); } } // This code is contributed by ratiagrawal.
Python3 from typing import List Tuple def find_max_profit ( jobs : List [ Tuple [ int int int ]]) -> int : n = len ( jobs ) # Sort the jobs in ascending order of their finish times jobs . sort ( key = lambda x : x [ 1 ]) # Initialize DP array with the first job and its profit as the maximum profit DP = [{ 'value' : jobs [ 0 ][ 2 ] 'jobs' : [ jobs [ 0 ]]}] # Iterate over the remaining jobs for i in range ( 1 n ): # Find the index of the latest non-conflicting job l = latest_non_conflict ( jobs i ) # Calculate the profit that can be obtained by including the current job incl_prof = jobs [ i ][ 2 ] if l != - 1 : incl_prof += DP [ l ][ 'value' ] # Update DP array with the maximum profit and set of jobs if incl_prof > DP [ i - 1 ][ 'value' ]: DP . append ({ 'value' : incl_prof 'jobs' : DP [ l ][ 'jobs' ] + [ jobs [ i ]]}) else : DP . append ( DP [ i - 1 ]) # Print the optimal set of jobs and the maximum profit obtained print ( 'Optimal Jobs for maximum profits are' ) for j in DP [ - 1 ][ 'jobs' ]: print ( f '( { j [ 0 ] } { j [ 1 ] } { j [ 2 ] } )' ) print ( f ' n Total Optimal profit is { DP [ - 1 ][ 'value' ] } ' ) def latest_non_conflict ( jobs : List [ Tuple [ int int int ]] index : int ) -> int : lo hi = 0 index - 1 while lo <= hi : mid = ( lo + hi ) // 2 if jobs [ mid ][ 1 ] <= jobs [ index ][ 0 ]: if jobs [ mid + 1 ][ 1 ] <= jobs [ index ][ 0 ]: lo = mid + 1 else : return mid else : hi = mid - 1 return - 1 # Test the program with a different set of jobs jobs = [( 3 5 20 ) ( 1 2 50 ) ( 6 19 100 ) ( 2 100 200 )] find_max_profit ( jobs ) # This code is contributed by divyansh2212
C# using System ; using System.Collections.Generic ; public class WeightedJobScheduling { // A job has start time finish time and profit. class Job { public int start finish profit ; public Job ( int start int finish int profit ) { this . start = start ; this . finish = finish ; this . profit = profit ; } } // to store subset of jobs class weightedJob { // vector of Jobs public List < Job > job ; // find profit associated with included Jobs public int value ; public weightedJob () { job = new List < Job > (); } } // A utility function that is used for sorting events // according to finish time class JobComparator : IComparer < Job > { public int Compare ( Job j1 Job j2 ) { return j1 . finish - j2 . finish ; } } // A Binary Search based function to find the latest job // (before current job) that doesn't conflict with // current job. 'index' is index of the current job. // This function returns -1 if all jobs before index // conflict with it. The array jobs[] is sorted in // increasing order of finish time static int latestNonConflict ( Job [] jobs int index ) { // Initialize 'lo' and 'hi' for Binary Search int lo = 0 hi = index - 1 ; // Perform binary Search iteratively while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( jobs [ mid ]. finish <= jobs [ index ]. start ) { if ( jobs [ mid + 1 ]. finish <= jobs [ index ]. start ) { lo = mid + 1 ; } else { return mid ; } } else { hi = mid - 1 ; } } return - 1 ; } // The main function that finds the subset of jobs // associated with maximum profit such that no two // jobs in the subset overlap. static int findMaxProfit ( Job [] arr ) { // Sort jobs according to finish time Array . Sort ( arr new JobComparator ()); // Create an array to store solutions of // subproblems. DP[i] stores the Jobs involved and // their total profit till arr[i] (including arr[i]) weightedJob [] DP = new weightedJob [ arr . Length ]; DP [ 0 ] = new weightedJob (); // initialize DP[0] to arr[0] DP [ 0 ]. value = arr [ 0 ]. profit ; DP [ 0 ]. job . Add ( arr [ 0 ]); // Fill entries in DP[] using recursive property for ( int i = 1 ; i < arr . Length ; i ++ ) { // Find profit including the current job int inclProf = arr [ i ]. profit ; int l = latestNonConflict ( arr i ); if ( l != - 1 ) { inclProf += DP [ l ]. value ; } // Store maximum of including and excluding if ( inclProf > DP [ i - 1 ]. value ) { DP [ i ] = new weightedJob (); DP [ i ]. value = inclProf ; DP [ i ]. job . AddRange ( DP [ l ]. job ); DP [ i ]. job . Add ( arr [ i ]); } else { DP [ i ] = DP [ i - 1 ]; } } // DP[n - 1] stores the result Console . WriteLine ( 'Optimal Jobs for maximum profits are' ); foreach ( Job j in DP [ arr . Length - 1 ]. job ) { Console . WriteLine ( '(' + j . start + ' ' + j . finish + ' ' + j . profit + ')' ); } Console . WriteLine ( 'nTotal Optimal profit is ' + DP [ arr . Length - 1 ]. value ); return DP [ arr . Length - 1 ]. value ; } // Driver program static void Main ( string [] args ) { Job [] arr = { new Job ( 3 5 20 ) new Job ( 1 2 50 ) new Job ( 6 19 100 ) new Job ( 2 100 200 ) }; findMaxProfit ( arr ); } } // This code is contributed by lokeshpotta20.
JavaScript const findMaxProfit = ( jobs ) => { // Store the number of jobs const n = jobs . length ; // Sort the jobs in ascending order of their finish times jobs . sort (( a b ) => a [ 1 ] - b [ 1 ]); // Initialize DP array with the first job and its profit as the maximum profit let DP = [{ value : jobs [ 0 ][ 2 ] jobs : [ jobs [ 0 ]] }]; // Iterate over the remaining jobs for ( let i = 1 ; i < n ; i ++ ) { // Find the index of the latest non-conflicting job const l = latestNonConflict ( jobs i ); // Calculate the profit that can be obtained by including the current job let inclProf = jobs [ i ][ 2 ]; if ( l !== - 1 ) { inclProf += DP [ l ]. value ; } // Update DP array with the maximum profit and set of jobs if ( inclProf > DP [ i - 1 ]. value ) { DP . push ({ value : inclProf jobs : DP [ l ]. jobs . concat ([ jobs [ i ]]) }); } else { DP . push ( DP [ i - 1 ]); } } // Print the optimal set of jobs and the maximum profit obtained console . log ( 'Optimal Jobs for maximum profits are' ); for ( const j of DP [ DP . length - 1 ]. jobs ) { console . log ( `( ${ j [ 0 ] } ${ j [ 1 ] } ${ j [ 2 ] } )` ); } console . log ( `nTotal Optimal profit is ${ DP [ DP . length - 1 ]. value } ` ); }; const latestNonConflict = ( jobs index ) => { let lo = 0 ; let hi = index - 1 ; while ( lo <= hi ) { const mid = Math . floor (( lo + hi ) / 2 ); if ( jobs [ mid ][ 1 ] <= jobs [ index ][ 0 ]) { if ( jobs [ mid + 1 ][ 1 ] <= jobs [ index ][ 0 ]) { lo = mid + 1 ; } else { return mid ; } } else { hi = mid - 1 ; } } return - 1 ; }; // Test the program with a different set of jobs const jobs = [[ 3 5 20 ] [ 1 2 50 ] [ 6 19 100 ] [ 2 100 200 ]]; findMaxProfit ( jobs ); // This code is contributed by unstoppablepandu.
Ausgabe
Optimal Jobs for maximum profits are (1 2 50) (2 100 200) Total Optimal profit is 250
Zeitkomplexität: O(n log n)
Hilfsraum: An)
