Office中国论坛/Access中国论坛

标题: [高4]一个算法问题. [打印本页]

作者: Roadbeg 时间: 2003-4-18 18:00
标题: [高4]一个算法问题.
若由两个人 a,b 承担 n 个作业的任务.设 a 处理第 i 个作业需时 ai, b 需时 bi.
对于某些 i ,有 ai>=bi,而对于某些 j (i<>j),又有 aj<bj
规定一个人不可能同时处理两个任务,一个任务也不可能分开由两个人完成.
请设计一个算法 , 求 a,b 处理 n 的最短时间及方法.

此题目抄自 2003 年第14期电脑报.

数据库设计时,架构思路最重要.
同样的,编程时算法最重要,请各位高手出招!

作者: baije 时间: 2003-5-31 21:02
有没规定要顺次做?
或规定要同时完成,
是要合计时间最短,
还是要两人从开始到两人都结束的时间最短?

作者: sunjy 时间: 2004-6-15 20:56
1.数据结构

任务ID       a用时间    b用时间    a和b用时间差(a-b)

  1             a(i)             b(i)          a(i)-b(i)

............................

2.排序，按照 "a和b用时间差"从大到小排序。

3.从两头循环累加，任务1开始的循环累加到变量tb，从任务n开始的循环累加到变量ta

循环中保证ta,tb相差最小。分光所有任务为止。

作者: Trynew 时间: 2005-6-20 18:17
由a在所有任务中取任意0至n个的组合，则余下的由b完成，遍历所有可能的组合，求出两人相加的时间为最小即可。其算法与下面贴子相似，只是判断的条件有所不同:http://www.office-cn.net/forum.php?mod=viewthread&tid=28439计算机算法通常就是进行循环遍历所有的可能组合或排列，进行比较。

作者: ganrong 时间: 2005-6-27 17:41
提示: 作者被禁止或删除内容自动屏蔽

作者: LucasLynn 时间: 2005-8-3 18:48

以下是引用sunjy在2004-6-15 12:56:00的发言：

1.数据结构

任务ID       a用时间    b用时间    a和b用时间差(a-b)

  1             a(i)             b(i)          a(i)-b(i)

............................

2.排序，按照 "a和b用时间差"从大到小排序。

3.从两头循环累加，任务1开始的循环累加到变量tb，从任务n开始的循环累加到变量ta

循环中保证ta,tb相差最小。分光所有任务为止。

这个算法应该是效率最高的。

作者: LucasLynn 时间: 2005-8-3 18:50

以下是引用Trynew在2005-6-20 10:17:00的发言：

由a在所有任务中取任意0至n个的组合，则余下的由b完成，遍历所有可能的组合，求出两人相加的时间为最小即可。

其算法与下面贴子相似，只是判断的条件有所不同:

http://www.office-cn.net/forum.php?mod=viewthread&tid=28439

计算机算法通常就是进行循环遍历所有的可能组合或排列，进行比较。

如果用遍历，这就不是一道算法题目，而是一个简单的数据结构实现了。很多情况下，用遍历的效率会低得吓人，比方说这个例子中，如果N>1000的，用遍历几乎不可能在1个小时内完成计算。因此计算机时代还是需要我们优化算法。ACM精神只有在特定的情况下才适用。

作者: J-2006 时间: 2006-3-30 04:52
[em06]

作者: lxh1968 时间: 2008-5-17 00:36
好好学习，天天向上。

作者: open0 时间: 2008-10-20 15:22
it 's asp

欢迎光临 Office中国论坛/Access中国论坛 (http://www.office-cn.net/)