有期限的作业排序问题
在此问题中，给出了一份作业列表。在列表中，还列出了每个工作的截止日期和利润。每个工作将占用一个单位时间，因此，一个工作的最短期限是1。如果一次只能安排一个工作，则可以最大程度地提高利润。
为了解决该问题，生成作业组的所有子集以检查单个子集是否可行。此外，跟踪已生成的所有可行子集的最大利润。
该算法的时间复杂度为O（n^2）
输入输出
Input:
A list of jobs with job id, deadline and profit. And the number of jobs n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output:
Following is maximum profit sequence of job sequence: c a e算法
jobSequence(jobList, n)
输入-作业列表以及列表中存在的作业数。
输出-顺序，如何进行作业。
Begin
sort the jobs in jobList according to their profit create a list of job sequence and slot to track free time slots
initially make all slots are free
for all given jobs i do
for all jobs in the list from ending of the list do
if slot[j] is free then
jobSequence[j] := i
make slot[j] := fill
break the loop
done
done
for all slots when it is not free do
print id of job using jobList[jobSequence[i]]
done
End示例
#include<iostream>
#include<algorithm>
using namespace std;
struct Job {
char id;
int deadLine;
int profit;
};
bool comp(Job j1, Job j2) {
return (j1.profit > j2.profit); //compare jobs based on profit
}
int min(int a, int b) {
return (a<b)?a:b;
}
void jobSequence(Job jobList[], int n) {
sort(jobList, jobList+n, comp); //sort jobList on profit
int jobSeq[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
for (int i=0; i<n; i++)
slot[i] = false; //initially all slots are free
for (int i=0; i<n; i++) { //for all given jobs
for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) { //search from last free slot
if (slot[j]==false) {
jobSeq[j] = i; // Add this job to job sequence
slot[j] = true; // mark this slot as occupied
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout << jobList[jobSeq[i]].id << " "; //display the sequence
}
int main() {
Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
int n = 5;
cout << "Following is maximum profit sequence of job sequence: ";
jobSequence(jobList, n);
}输出结果
Following is maximum profit sequence of job sequence: c a e