设为首页收藏本站Access中国

Office中国论坛/Access中国论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

返回列表 发新帖
查看: 7560|回复: 9

[高4]一个算法问题.

[复制链接]
发表于 2003-4-18 18:00:00 | 显示全部楼层 |阅读模式
若由两个人 a,b 承担 n 个作业的任务.设 a 处理第 i 个作业需时 ai, b 需时 bi.
对于某些 i ,有 ai>=bi,而 对于某些 j (i<>j),又有 aj<bj
规定一个人不可能同时处理两个任务,一个任务也不可能分开由两个人完成.
请设计一个算法 , 求 a,b 处理 n 的最短时间及方法.

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

数据库设计时,架构思路最重要.
同样的,编程时算法最重要,请各位高手出招!
发表于 2003-5-31 21:02:00 | 显示全部楼层
有没规定要顺次做?
或规定要同时完成,
是要合计时间最短,
还是要两人从开始到两人都结束的时间最短?
发表于 2004-6-15 20: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相差最小。分光所有任务为止。

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

点击这里给我发消息

发表于 2005-6-27 17:41:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
发表于 2005-8-3 18:48:00 | 显示全部楼层
以下是引用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相差最小。分光所有任务为止。

  





这个算法应该是效率最高的。
发表于 2005-8-3 18:50:00 | 显示全部楼层
以下是引用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精神只有在特定的情况下才适用。
发表于 2006-3-30 04:52:00 | 显示全部楼层
[em06]
发表于 2008-5-17 00:36:31 | 显示全部楼层
好好学习,天天向上。
发表于 2008-10-20 15:22:27 | 显示全部楼层
it 's asp
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|站长邮箱|小黑屋|手机版|Office中国/Access中国 ( 粤ICP备10043721号-1 )  

GMT+8, 2024-3-29 14:36 , Processed in 0.081142 second(s), 34 queries .

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表