모든 직업이 다음 세 가지 요소로 표현되는 N개의 직업이 있다고 가정합니다.
1. 시작 시간
2. 종료 시간
3. 관련 이익 또는 가치
하위 집합에 있는 두 개의 직업이 겹치지 않도록 직업의 최대 이익 하위 집합을 찾습니다.
예:
자바 정렬 배열
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.
~ 안에 이전의 게시물에서 우리는 Weighted Job Scheduling 문제에 대해 논의했습니다. 우리는 현재 직업을 기본적으로 포함하거나 제외하는 DP 솔루션에 대해 논의했습니다. 이 게시물에서는 작업을 인쇄하는 또 다른 흥미로운 DP 솔루션에 대해 논의합니다. 이 문제는 표준의 변형입니다. 가장 긴 증가 부분 수열(LIS) 문제. LIS 문제의 동적 프로그래밍 솔루션에 약간의 변화가 필요합니다.
먼저 시작 시간에 따라 작업을 정렬해야 합니다. job[0..n-1]을 정렬 후 작업 배열로 둡니다. L[i] 자체가 job[i]로 끝나는 job[0..i]의 Weighted Job Scheduling을 저장하는 벡터가 되도록 벡터 L을 정의합니다. 따라서 인덱스 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).
jdbc jdbc