Vzhľadom na N pracovných miest, kde každé pracovné miesto je reprezentované nasledujúcimi tromi prvkami.
1. Čas začiatku
2. Čas ukončenia
3. Zisk alebo hodnota spojená
Nájdite podmnožinu úloh s maximálnym ziskom tak, aby sa žiadne dve úlohy v podmnožine neprekrývali.
Príklady:
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 predchádzajúce príspevok sme diskutovali o probléme váženého plánovania úloh. Diskutovali sme o riešení DP, kde v podstate zahŕňame alebo vylučujeme súčasnú prácu. V tomto príspevku sa diskutuje o ďalšom zaujímavom riešení DP, kde tiež tlačíme úlohy. Tento problém je variáciou štandardu Najdlhšia rastúca podsekvencia (LIS) problém. Potrebujeme malú zmenu v riešení dynamického programovania problému LIS.
Najprv musíme zoradiť úlohy podľa času začiatku. Nech job[0..n-1] je pole úloh po zoradení. Vektor L definujeme tak, že L[i] je sám o sebe vektor, ktorý ukladá vážené plánovanie úloh úlohy[0..i], ktorá končí úlohou[i]. Preto pre index i L[i] možno rekurzívne zapísať ako -
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
Zvážte napríklad dvojice {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}
Vyberáme vektor s najvyšším ziskom. V tomto prípade L[1].
Nižšie je uvedená implementácia vyššie uvedenej myšlienky -
C++// C++ program for weighted job scheduling using LIS #include
// 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 sanjeev2552
# 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)
using 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); } }
// JavaScript program for weighted job scheduling using LIS // A job has start time finish time and profit. function Job(start finish profit) { this.start = start; this.finish = finish; this.profit = profit; } // Utility function to calculate sum of all vector // elements function findSum(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i].profit; } return sum; } // comparator function for sort function function compare(x y) { return x.start < y.start; } // The main function that finds the maximum possible // profit from given array of jobs function findMaxProfit(arr) { // Sort arr[] by start time. arr.sort(compare); // L[i] stores Weighted Job Scheduling of // job[0..i] that ends with job[i] let L = new Array(arr.length).fill([]); // L[0] is equal to arr[0] L[0] = [arr[0]]; // start from index 1 for (let i = 1; i < arr.length; i++) { // for every j less than i for (let 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(arr[i]); } let maxChain = []; // find one with max profit for (let i = 0; i < L.length; i++) { if (findSum(L[i]) > findSum(maxChain)) { maxChain = L[i]; } } for (let i = 0; i < maxChain.length; i++) { console.log( '(' + maxChain[i].start + ' ' + maxChain[i].finish + ' ' + maxChain[i].profit + ') ' ); } } // Driver Function let a = [ new Job(3 10 20) new Job(1 2 50) new Job(2 100 200) ]; findMaxProfit(a);
Výstup
(1 2 50) (2 100 200)
Vyššie uvedené riešenie DP môžeme ďalej optimalizovať odstránením funkcie findSum(). Namiesto toho môžeme zachovať ďalší vektor/pole na uloženie súčtu maximálneho možného zisku do úlohy i.
Časová zložitosť vyššie uvedené riešenie dynamického programovania je O(n2), kde n je počet úloh.
Pomocný priestor používaný programom je O(n2).