加权作业调度|集2（使用LIS）-yiteyi-C++库

给定N个作业，其中每个作业由以下三个元素表示。 1.开始时间 2.完成时间 3.相关利润或价值找到工作的最大利润子集，使子集中没有两个工作重叠。

null

例如：

Input:  Number of Jobs n = 4Job 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.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

在里面以前的之后，我们讨论了加权作业调度问题。我们讨论了一个DP解决方案，基本上包括或不包括当前工作。在这篇文章中，我们还讨论了另一个有趣的DP解决方案，我们也在这里打印作业。这个问题是标准的变化最长递增子序列（LIS）问题我们需要对LIS问题的动态规划解法稍作修改。

我们首先需要根据开始时间对工作进行排序。让作业[0..n-1]成为排序后的作业数组。我们定义了向量L，使得L[i]本身是一个向量，它存储以作业[i]结尾的作业[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 <iostream>                       
                         #include <vector>                       
                         #include <algorithm>                       
                         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 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;                       
                         }                       

JAVA

                         // 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 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)"                                     ,                       
                                                 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                       

输出：

(1, 2, 50) (2, 100, 200)

我们可以通过删除findSum（）函数来进一步优化上述DP解决方案。相反，我们可以维护另一个向量/数组来存储作业i之前可能的最大利润之和在这里 .

时间复杂性 上面的动态规划解是O（n） ^2. )其中n是工作的数量。 辅助空间 程序使用的是O（n） ^2. ).

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章