[高4]一个算法问题.

Roadbeg

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

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

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

baije

有没规定要顺次做?
或规定要同时完成,
是要合计时间最短,
还是要两人从开始到两人都结束的时间最短?

sunjy

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

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

LucasLynn

以下是引用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

以下是引用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

[em06]

lxh1968

好好学习，天天向上。

open0

it 's asp