N 個のジョブが与えられ、すべてのジョブは次の 3 つの要素で表されます。
1. 開始時間
2. 終了時間
3. 関連する利益または価値
サブセット内の 2 つのジョブが重ならないように、ジョブの最大利益サブセットを見つけます。
スプリング ブートの注釈
例:
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.
で 前の この投稿では、加重ジョブ スケジューリングの問題について説明しました。基本的に現在の仕事を含めるか除外する DP ソリューションについて話し合いました。この投稿では、ジョブを印刷する別の興味深い DP ソリューションについて説明します。この問題は標準の問題のバリエーションです 最長増加サブシーケンス (LIS) 問題。 LIS 問題の動的プログラミングの解決策に少し変更を加える必要があります。
まず、ジョブを開始時間に従って並べ替える必要があります。 job[0..n-1] をソート後のジョブの配列とします。ベクトル L を、L[i] 自体が、job[i] で終わる job[0..i] の加重ジョブ スケジューリングを格納するベクトルであるように定義します。したがって、インデックス i に対して L[i] は再帰的に次のように書くことができます -
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
たとえば、ペア {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}
利益が最も高いベクトルを選択します。この場合、L[1]。
以下は上記のアイデアの実装です –
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);
出力
(1 2 50) (2 100 200)
findSum() 関数を削除することで、上記の DP ソリューションをさらに最適化できます。代わりに、ジョブ i までに可能な最大利益の合計を保存する別のベクトル/配列を維持できます。
時間計算量 上記の動的計画法ソリューションは O(n2) ここで、n はジョブの数です。
補助スペース プログラムで使用されるのは O(n2）。