工作排序问题——损失最小化

我们得到了编号为1到N的N个工作。对于每个活动，让Ti表示完成工作所需的天数。在开始为工作i工作之前，每延迟一天，就会损失一个李。 我们需要找到一个顺序来完成这些工作，以便将总体损失降至最低。我们一次只能做一件工作。

如果有多个这样的解决方案是可能的，那么我们需要给出字典最小排列（即字典顺序中最早的排列）。

例如：

Input : L = {3, 1, 2, 4} and 
        T = {4, 1000, 2, 5}
Output : 3, 4, 1, 2
Explanation: We should first complete 
job 3, then jobs 4, 1, 2 respectively.

Input : L = {1, 2, 3, 5, 6} 
        T = {2, 4, 1, 3, 2}
Output : 3, 5, 4, 1, 2 
Explanation: We should complete jobs 
3, 5, 4, 1 and then 2 in this order.

让我们考虑两个极端情况，我们将从它们推导出一般情况解。

1. 所有工作需要相同的时间完成，即Ti=k表示所有i。由于所有工作需要相同的时间完成，我们应该首先选择损失较大（Li）的工作。我们应该选择损失最大的工作，并尽早完成。 因此，这是一个贪婪的算法。仅根据Li按降序排列作业。
2. 所有工作都有相同的惩罚。因为所有的工作都有相同的惩罚，我们会先做那些需要较少时间完成的工作。这将最大限度地减少总延误，从而减少总损失。 这也是一个贪婪算法。根据Ti按升序排序作业。或者我们也可以按1/Ti的降序排序。

   从上面的例子中，我们可以很容易地看到，我们应该把工作分类，而不仅仅是基于Li或Ti。相反，我们应该根据Li/Ti的比率，按降序对工作进行排序。

   如果我们执行一个任务，我们可以得到按字典顺序排列的最小任务 稳定排序 关于工作。稳定排序的一个例子是 合并排序 .

   为了得到最准确的结果，避免将Li除以Ti。相反，将这两个比率像分数一样进行比较。要比较a/b和c/d，请比较ad和bc。

   // CPP program to minimize loss using stable sort. #include <iostream> #include <algorithm> #include <vector> using namespace std; #define all(c) c.begin(), c.end() // Each job is represented as a pair of int and pair. // This is done to provide implementation simplicity // so that we can use functions provided by algorithm // header typedef pair< int , pair< int , int > > job; // compare function is given so that we can specify // how to compare a pair of jobs bool cmp_pair(job a, job b) { int a_Li, a_Ti, b_Li, b_Ti; a_Li = a.second.first; a_Ti = a.second.second; b_Li = b.second.first; b_Ti = b.second.second; // To compare a/b and c/d, compare ad and bc return (a_Li * b_Ti) > (b_Li * a_Ti); } void printOptimal( int L[], int T[], int N) { vector<job> list; // (Job Index, Si, Ti) for ( int i = 0; i < N; i++) { int t = T[i]; int l = L[i]; // Each element is: (Job Index, (Li, Ti) ) list.push_back(make_pair(i + 1, make_pair(l, t))); } stable_sort(all(list), cmp_pair); // traverse the list and print job numbers cout << "Job numbers in optimal sequence are" ; for ( int i = 0; i < N; i++) cout << list[i].first << " " ; } // Driver code int main() { int L[] = { 1, 2, 3, 5, 6 }; int T[] = { 2, 4, 1, 3, 2 }; int N = sizeof (L) / sizeof (L[0]); printOptimal(L, T, N); return 0; }

   输出：

   Job numbers in optimal sequence are
   3 5 4 1 2 
   

   时间复杂度：O（N logn） 空间复杂性：O（N）

   本文由 萨扬·马哈帕特拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

   如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。