首页 > 试题广场 >

假设有 n 个人需排队等候处理事务,已知每个人需要处理的时间

[问答题]
假设有 n 个人需排队等候处理事务,已知每个人需要处理的时间为 ti,(0<i<=n),请给出一种最优排队次序,使所有人排队等候的总时间最小。
要求:
(1). 给出你的贪心选择策略;
(2). 证明贪心选择的正确性;
(3). 写出解此问题的贪心算法。
短事务优先
发表于 2023-01-28 20:20:06 回复(0)
要求总时间最少,考虑两个极限的情况,时间长的往前排和时间短的往前排,总时间为tn·n求和,tn应该随着n的减小而增大,总时间才会最小
发表于 2017-09-17 00:56:25 回复(0)