首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

也是tencent附加题,该如何解决

2012-02-05 
也是tencent附加题一处理机有total个存储空间,现要处理N个任务,每个任务计算占C个空间,存储用S个空间其中(

也是tencent附加题
一处理机有total个存储空间,现要处理N个任务,每个任务计算占C个空间,存储用S个空间其中(C>S),设计一算法,求出这处理机能否完成这deal个任务,如果能,应该如何安排任务。

[解决办法]
C-S的逆序
[解决办法]
假设最佳执行顺序为 N1,N2,N3…Ni…Nj…

则执行完前Nj个任务之后,所剩余的空间是执行完N1到Nj所有j个任务之后所能剩余的最大空间(对于前j个任务的任意排列来说)。先从N1,N2开始看。假设N1计算时需要Cn1空间,存储时需要Sn1空间,N2分别需要Cn2,Sn2,假设Cn1-Sn1<=Cn2-Sn2,则Cn1+Sn2<=Cn2+Sn1,Cn1+Sn2就是先执行完第n2之后再执行n1所需要的总体的空间,不等式后边则是先执行完n1再执行n2所需要的总体的空间,显然先执行完n2再执行n1要比先执行n1再执行n2时需要的空间要少。

当执行n3时,需要空间为Sn1+Sn2+Cn3,若Cn3-Sn3<=Cn2-Sn2,则Cn3+Sn2<=Cn2+Sn3,假如按照n1 n3 n2的顺序进行的话,则需要Sn1+Sn3+Cn2的空间,由于Cn3+Sn2<=Cn2+Sn3,所以Sn1+Sn3+Cn2>=Sn1+Sn2+Cn3,所以n1 n3 n2的顺序要比n1,n2,n3的顺序要差(也就是说当执行此序列的最后一个任务时需要的空间更多)。同理可证,当出现其它排列时,也会大于等于n1,n2,n3的顺序。所以满足规律:按照每个任务i的Ci-Si进行从大到小排序组成的执行序列n1,n2,n3是最佳序列

假设此序列的前j个任务都满足此规律(对于序列中的每个任务i来说Ci-Si都不大于此序列中该任务前面任何任务k的Ck-Sk),对于第j+1个任务N(j+1)来说,假如N(j+1)与Ni互换的话,则当此序列执行到第j+1个任务时需要的空间为Sn1+Sn2+…+Sn(j+1)+…+Snj+Cni(1),而如果按照我们假设的最佳序列执行时需要Sn1+Sn2+…+Sni+…Snj+Cn(j+1)(2),因为Cni-Sni>=Cn(j+1)-Sn(j+1),所以Cni+Sn(j+1)>=Cn(j+1)+Sni,则(1)>=(2)。由此可以证明该最佳序列满足规律:按照每个任务i的Ci-Si进行从大到小排序组成的执行序列位最佳执行序列

总结:满足按照Ci-Si进行由大到小排列的执行序列为最佳序列

热点排行