带有期限的作业排序问题(贪心)-摩杜云开发者社区

转载【算法设计】带有期限的作业排序（贪心算法）_带时限的作业排序贪心算法-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;
}