Problem statement:
問題陳述：
Given an array of jobs where every job has a deadline and a profit. Profit can be earned only if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time. Print the sequence of jobID order to maximize total profit.
給定一系列工作，每個工作都有截止日期和利潤。 只有在截止日期之前完成工作，才能賺取利潤。 還假定每個工作都占用一個單位時間，因此任何工作的最小可能截止期限為1。如果一次只能安排一個工作，那么如何使總利潤最大化。 打印jobID訂單的順序以最大化總利潤。
Input example
輸入例
| JobID | Deadline | Profit |
|---|---|---|
| 1 | 4 | 30 |
| 2 | 2 | 20 |
| 3 | 2 | 60 |
| 4 | 2 | 30 |
| 5 | 1 | 10 |
| 6 | 4 | 80 |
| 職位編號 | 最后期限 | 利潤 |
|---|---|---|
| 1個 | 4 | 30 |
| 2 | 2 | 20 |
| 3 | 2 | 60 |
| 4 | 2 | 30 |
| 5 | 1個 | 10 |
| 6 | 4 | 80 |
Output example: 4 3 1 6
輸出示例：4 3 1 6
Problem explanation:
問題說明：
First of all, forget about the greedy algorithm. Let’s just solve with our intuition. Since the problem is to maximize profit intuition says to select jobs in decreasing order according to their profit. That means to select the maximum profit one first, then the 2nd maximum profit one and so on. While selecting jobs we only need to keep track whether it can be finished in deadline.
首先，忘掉貪婪算法 。 讓我們憑直覺來解決。 由于問題在于最大化利潤，因此直覺表示要根據他們的利潤以降序選擇工作。 這意味著首先選擇一個最大利潤，然后選擇第二個最大利潤，依此類推。 在選擇工作時，我們只需要跟蹤它是否可以在截止日期之前完成。
So let’s start...
所以我們開始吧...
It can be seen from the job table that, there are four jobs with the scheduled deadline at most 2. Thus we can only select a maximum of 2 jobs from these 4 jobs since each job take 1 unit time to process. (local observation)
從作業表中可以看到，有四個作業的排定的截止日期最多為2個。因此，由于每個作業需要1個單位時間來處理，因此我們只能從這4個作業中最多選擇2個作業。 (當地觀察)
At time 0:
在時間0：
Select maximum profit one with deadline at most 2
Job id: 3, deadline: 2, valid choice, process the job
Profit at time 0 : 60
選擇最大利潤之一，截止日期最多為2
職位編號：3，截止日期：2，有效選擇，處理職位
時間0：60的利潤
At time 1:
在時間1：
Select maximum profit one from remaining jobswith deadline at most 2
Job id: 4, deadline: 2, valid choice, process the job
Profit at time 1 : 60+30
That’s why can’t choose job with ID 5 & 2
從剩余工作中選擇最大利潤之一，截止日期最多為2
職位編號：4，期限：2，有效選擇，處理職位
時間1的利潤：60 + 30
這就是為什么不能選擇ID 5和2的工作
At time 2:
在時間2：
Select maximum from remaining one with deadline greater than 2
Job id: 6, deadline: 4, valid choice, process the job
Profit at time 2 : 60+30+80
從截止日期大于2的剩余一項中選擇最大值
職位編號：6，截止日期：4，有效選擇，處理職位
時間2的利潤：60 + 30 + 80
At time 3:
在時間3：
Select job
With job id: 1, deadline : 4, valid choice, process the job
Job sequence : 3 4 6 1
Finally total profit= 60+30+80+30=200
選擇工作
職位編號：1，截止日期：4，有效選擇，處理職位
作業順序：3 4 6 1
最終總利潤= 60 + 30 + 80 + 30 = 200
No other choice could have resulted better (you can check it!!!!). Thus the solution is optimized and we have found the maximum solution.
沒有其他選擇可以產生更好的效果(您可以檢查！！！！)。 因此，解決方案已經過優化，我們找到了最大的解決方案。
Now, revise what we have done. We have actually sorted the job table according to max profit & then have made the local best choice at each iteration to reduce the problem size & ultimately to reach the goal. Simply speaking, we have used the greedy technique intuitively & greedy algorithm has successfully solved the job sequencing problem.
現在，修改我們所做的。 我們實際上已經根據最大利潤對作業表進行了排序，然后在每次迭代中都做出了局部最佳選擇，以減少問題的規模并最終達到目標。 簡而言之，我們直觀地使用了貪婪技術 ，貪婪算法成功解決了工作排序問題。
Now to code simply follow the below steps which are nothing but what we did solving the previous example:
現在，只需按照以下步驟進行編碼，這些步驟不過是我們解決上一個示例所做的工作：
Create a class to define jobs
創建一個類來定義作業
class job { public: int jobid; //job id int deadline; //deadline int profit; //profit of the job };To take input we have used the concept of array of pointers to the job objects. job *obj[n]; //array of pointer to jobs(jobs namely)
為了接受輸入，我們使用了指向作業對象的指針數組的概念。 工作* obj [n]; //指向作業的指針數組(即作業)
maxProfit function()
maxProfit函數()
- Sort all jobs in decreasing order of profit.
bool mycompare(job *x,job *y)//boolean function { //sort as per decreasing profite return x->profit>y->profit; } sort(obj,obj+n,mycompare);Find the maximum deadline, let it be max.
找到最大截止日期，使其為max 。
Create store[max] to store job sequence
創建store [max]以存儲作業序列
Create slot[max] to mark occupied slots
創建slot [max]以標記占用的插槽
For i=0:no of jobs
對于i = 0：沒有工作
// now pick the job with max deadline from // that deadline traverse array backto find an empty slot for(int j=(obj[i]->deadline)-1;j>=0;j--) { if(slot[j]==false){ // slot is empty // count the total profit profit+=obj[i]->profit; store[j]=obj[i]->jobid; slot[j]=true; break; } }Print the store array to find job sequence and print profit which is maximum profit output
打印商店數組以查找工作順序并打印利潤 (最大利潤輸出)
C ++實現作業排序問題 (C++ implementation of Job sequencing problem)
#include<bits/stdc++.h>
using namespace std;
// define the class for the job
class job
{
public:
int jobid;
int deadline;
int profit;
};
// our compare function to sort
bool mycompare(job *x,job *y)//boolean function
{
//sort as per decreasing profit
return x->profit>y->profit;
}
int maxProfit(job** obj,int n){
int max=0,profit=0;;
//find maximum deadline
for(int i=0;i<n;i++){
if(i==0){
max=obj[i]->deadline;
}
else{
if(obj[i]->deadline>max)
max=obj[i]->deadline;
}
}
sort(obj,obj+n,mycompare);
// create array of max deadline size
int store[max]={0}; // empty array initially
bool slot[max]={false}; //all slots empty initially
for(int i=0;i<n;i++)
{
// now pick the job with max deadline and from
// that deadline traverse array back to find an empty slot
for(int j=(obj[i]->deadline)-1;j>=0;j--)
{
if(slot[j]==false) // slot is empty
{
// count the total profit
profit+=obj[i]->profit;
store[j]=obj[i]->jobid;
slot[j]=true;
break;
}
}
}
// printing the job sequence
cout<<"jobs sequence is:"<<"\t";
for(int i=0;i<max;i++)
{
if(slot[i])
cout<<store[i]<<" ";
}
return profit; //return profit
}
int main()
{
int n,size,max,totalprofit=0;
cout<<"enter the no. of jobs:";
cin>>n;
job *obj[n]; //array of pointer to jobs(jobs namely)
// user input and finding maximum deadline
for(int i=0;i<n;i++)
{
obj[i]=(job*)malloc(sizeof(struct job));
cout<<"enter jobid,deadline and profit of job "<<i+1<<endl;
cin>>obj[i]->jobid;
cin>>obj[i]->deadline;
cin>>obj[i]->profit;
}
totalprofit=maxProfit(obj,n); //total profit
cout<<"\ntotal profit is "<<totalprofit<<"\n";
return 0;
}
Output
輸出量
enter the no. of jobs:6
enter jobid,deadline and profit of job 1
1 4 30
enter jobid,deadline and profit of job 2
2 2 20
enter jobid,deadline and profit of job 3
3 2 60
enter jobid,deadline and profit of job 4
4 2 30
enter jobid,deadline and profit of job 5
5 1 10
enter jobid,deadline and profit of job 6
6 4 80
jobs sequence is: 4 3 1 6
total profit is 200
翻譯自: https://www.includehelp.com/icp/job-sequencing-problem.aspx
)
