带有期限的作业排序问题(贪心)

这篇具有很好参考价值的文章主要介绍了带有期限的作业排序问题(贪心)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

 文章来源地址https://www.toymoban.com/news/detail-748562.html

到了这里,关于带有期限的作业排序问题(贪心)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

    目录 (一)题目网址+视频网址  (二)手写草稿思考 Part1: 慕课PPT  Part2: 笨蛋的学习 北京大学网站在线算法题: 1042 -- Gone Fishing (poj.org) 视频讲解(北京大学附郭炜教授) : 程序设计与算法(二)算法基础_北京大学_中国大学MOOC(慕课) (icourse163.org) 老师的视频讲解,发现老

    2024年02月05日
    浏览(46)
  • 计算机算法分析与设计(14)---贪心算法(会场安排问题和最优服务次序问题)

     假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 数据输入: 第 1 1 1 行中有一个整数 n n n ,表示有 n n n 个待安排的活动。接下来的 n n n 行中,每行有 2 2 2 个正整数,分别表示 n n n 个待安排的活动的开始时间和结束

    2024年02月02日
    浏览(44)
  • 湘潭大学 算法设计与分析实验 回溯 动态规划 贪心 模拟退火解决背包问题

    https://download.csdn.net/download/SQ_ZengYX/88620871 测试用例

    2024年02月02日
    浏览(62)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(95)
  • 贪心算法问题实验:贪心算法解决TSP问题

    TSP问题是指旅行商问题,即给定一组城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中有着广泛的应用。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最

    2024年02月03日
    浏览(44)
  • 算法设计方法之贪心算法

    贪心算法是算法设计的一种方法。期盼通过每个阶段的局部最优选择,从而达到全局的最优。但结果不一定是最优的。 场景一 零钱兑换 现有硬币 1 元、2 元、5 元,需要用最少的硬币数量凑够 11 元。 利用贪心算法实现,优先考虑最好的结果就是面值为 5 元的硬币,11 = 5 +

    2024年02月17日
    浏览(46)
  • 【算法分析与设计】贪心算法(下)

      给定带权有向图G =(V,E),其中 每条边的权是非负实数 。另外,还给定V中的一个顶点,称为源。现在 要计算从源到所有其它各顶点的最短路长度 。 这里路的长度是指路上各边权之和 。 这个问题通常称为单源最短路径问题 。   Dijkstra算法是解单源最短路径问题的贪心

    2024年02月08日
    浏览(42)
  • 算法设计与分析之贪心算法

    贪心算法(Greedy Algorithm)是一种基于贪心思想的算法策略。它通过每一步选择当前状态下最优的解决方案,从而逐步得到全局最优解。贪心算法通常在问题具有 贪心选择性质 和 最优子结构性质 时被应用。 贪心算法的基本思想是,每一步选择当前情况下看起来最好的解决方

    2024年02月11日
    浏览(47)
  • 【算法分析与设计】贪心算法(上)

      理解贪心算法的概念。   掌握贪心算法的基本要素   (1) 最优子结构性质   (2) 贪心选择性质   理解贪心算法与动态规划算法的差异   理解贪心算法的一般理论   通过应用范例学习贪心设计策略。   (1) 活动安排问题 ;   (2) 最优装载问题

    2024年02月08日
    浏览(50)
  • 【四】【算法分析与设计】贪心算法的初见

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i ,都有一个胃口值 g[i] ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 s[j] 。如果 s[j] = g[i] ,我们可以将这个饼干 j 分配给孩子

    2024年03月17日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包