算法基础大作业.doc

算法基础大作业
全文10页1578字 叙述详尽
一．题目一：编程实现带有限期的作业排序

1. 描述：本题是利用贪心算法实现，应用贪心策略来解决操作系统中单机，无资源约束且每个作业可在等量的时间内完成的作业调度问题。即，假设只能在一台机器上处理n个作业，没个作业均可在单位时间内完成，又假定每个作业i都有一个截止期限di>0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获得pi>0的效益。这个问题的一个可行解是这n个作业的一个子集合J，J中的没个作业都能在各自的截止期限之前完成。可行解的效益值是J中这些作业的效益之和，即 。具有最大效益的可行解就是最优解。
大作业心得：
这次算法大作业，我做了有期限作业排序和和多段图向前向后处理法熟悉了贪心算法和求最小路径的问题，通过作业对一些程序的算法的有了一定了解，明白了学习算法的重要性！作业的过程是对课本的知识起到了很好的巩固作用，也学到了一些新的知识，在作业的过程中也遇到了一些困难，不过基本上都通过与同学讨论和查找资料解决了，是一个很好的学习过程，也极大的锻炼了我们实际动手的能力。有着书面考试无法比拟的优点。