2 michealpan michealpan 于 2016.03.30 20:25 提问

一个比较麻烦的任务调度问题
先上题:
    问题描述

  有若干个任务需要在一台机器上运行。它们之间没有依赖关系,因此 可以被按照任意顺序执行。
  该机器有两个 CPU 和一个 GPU。对于每个任务,你可以为它分配不 同的硬件资源:
  1. 在单个 CPU 上运行。
  2. 在两个 CPU 上同时运行。
  3. 在单个 CPU 和 GPU 上同时运行。
  4. 在两个 CPU 和 GPU 上同时运行。
  一个任务开始执行以后,将会独占它所用到的所有硬件资源,不得中 断,直到执行结束为止。第 i 个任务用单个 CPU,两个 CPU,单个 CPU 加 GPU,两个 CPU 加 GPU 运行所消耗的时间分别为 ai,bi,ci 和 di。
  现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。
输入格式
  输入的第一行只有一个正整数 n(1 ≤ n ≤ 40), 是总共需要执行的任 务个数。
  接下来的 n 行每行有四个正整数 ai, bi, ci, di(ai, bi, ci, di 均不超过 10), 以空格隔开。
输出格式
  输出只有一个整数,即完成给定的所有任务所需的最少时间。
样例输入
3
4 4 2 2
7 4 7 4
3 3 3 3
样例输出
7
样例说明
  有很多种调度方案可以在 7 个时间单位里完成给定的三个任务,以下是其中的一种方案:
  同时运行第一个任务(单 CPU 加上 GPU)和第三个任务(单 CPU), 它们分别在时刻 2 和时刻 3 完成。在时刻 3 开始双 CPU 运行任务 2,在 时刻 7 完成。

我刚开始学算法,对动态规划还不熟练,感觉这道题要用动态规划来做,却一直都找不到最优子结构,求大神点拨!

3个回答

flueky
flueky   2016.03.31 09:28

找不到最优子结构,那就不要用动态规划算法。关于任务调度算法,占用的资源多用的时间就少。既然需要你找出一个调度方案,用的时间最少,那就采取贪心算法,在当前做出最优选择。贪心算法选取调度方案原则:首先选择时间最少,其次选择占用资源最少。所以上述任务中,可供调度的方案有:a1/c1,a2/b2,a3。在执行任务的先后方便,若采用穷举法,那就是3!=6种方案,弃之。在选取任务时,建议画出三个时间轴辅助你思考。每选取一个任务要考虑到执行下一个任务时,中间空闲出来的时间。换句话说就是时间碎片最小化。所以答案很明显了。

michealpan
michealpan 我一开始也是这种思路去写,按照目前的状态去讨论下一组的状态。。但结果不对,因为后面的任务可能会影响前面几个任务的一组选择。。
一年多之前 回复
devmiao
devmiao   Ds   Rxr 2016.03.30 23:29
michealpan
michealpan 没悟透呀
一年多之前 回复
CSDNXIAOD
CSDNXIAOD   2016.03.30 20:32

一个任务调度问题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!