带有期限的作业排序问题(贪心)
转载【算法设计】带有期限的作业排序（贪心算法）_带时限的作业排序贪心算法-CSDN博客
主要是给自己加注释
已知：
n个作业，每个作业都有一个截止期限di，当且仅当作业i在它的期限截止以前被完成时，可获得pi的效益。
求：
可行解集合J
测试数据：
n=4，（p1，p2，p3，p4）=（100，20，15，10）；
（d1，d2，d3，d4）=（2，1，3，1）。
可行解：J=（2，1，3），p=100+20+15。
注：这里默认作业是按照效益p1>=p2>=p3……
如果效益随机输入，考虑使用结构体数组
函数实现：
void JS ( int D[ ], int J[ ], int n, int &k )；
数据存储：
1）D(1：n）是期限值【D(0)=0】，效益p集合一样，并且是非增次序；
2）J（i）是最优解中的第 i 个作业【J(0)=0】；
3）最终 J满足D[J(i)]<=D[J(i+1)]；
4）k 为J中可行解的个数。
算法描述：
1）作业 1 放入J[1]；
2）从第2个作业开始，
i）先根据期限大小，寻找作业 i 在 J 中的位置，D[J(i)]和 J 中已有作业的期限比较 d[J[r]] > d[i] && d[J[r]] != r （代码有注释）。从J的最后一个开始比较，i期限小则r--，使得J中期限不为增序。
ii）符合条件则 J(r+1:k)中作业序号，向后平移，空出J[r+1]，插入作业 i，k加一。
#include<iostream> using namespace std; #define N 5 void JS(int d[], int J[], int n, int &k) { int r; k = 1; J[1] = 1;//计入作业1 k就是说J里面已经放的作业数就是右边界 r是J中挪动的左边界 for (int i = 2; i <= N; i++) { r = k; while (d[J[r]] > d[i] && d[J[r]] != r)//寻找位置&& 想把(r,k]向右挪一个 如果J中第r个作业ddl就是r 那就挪不了了 { r = r - 1; }
//只有 ddl比第r个长或等于 而且起码比r大 if (d[J[r]] <= d[i] && d[i] > r)//d[i]>r表示在期限内 后面一个不是多此一举 111跑一下就知道 { for (int j = k; j > r; j--) { J[j + 1] = J[j];//向后平移 } J[r + 1] = i; k++; } } } int main() { int d[N], p[N], J[N] = { 0 }; //初始化 cout << N-1 << "个期限：" << endl; for (int i = 1; i < N; i++) { cin >> d[i]; } cout << N-1 << "个效益（降序）：" << endl;//降序 for (int i = 1; i < N; i++) { cin >> p[i]; } d[0] = p[0] = 0;//d(1:n)是期限值，p(1:n)并且是降序 int k;//个数 JS(d, J, N, k); for (int i = 1; i <= k; i++) { cout << "作业编号：" << J[i] << " 作业效益：" << p[J[i]] << " 作业期限：" << d[J[i]] << endl; } cout <<"可行解个数" << k << endl; return 0; }