转载【算法设计】带有期限的作业排序(贪心算法)_带时限的作业排序贪心算法-CSDN博客
主要是给自己加注释
文章来源:https://www.toymoban.com/news/detail-748562.html
已知:
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; }
文章来源地址https://www.toymoban.com/news/detail-748562.html
到了这里,关于带有期限的作业排序问题(贪心)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!