Home | Problems | Discuss | Login

  

老了,得想半天

3167: Computer

allen0815 | 2021-03-25 16:09:38 | delete | edit
设序列A=(t0,w0),(t1,w1),...,(tn,wn)为任务调度最优解
设F(a,b)为(ta,wa)到(tb,wb)的总代价

对于任意0<=i<n
交换(ti,wi),(t(i+1),w(i+1))的顺序得到新的总代价大于等于最优解,即
F(0,n)<=F(0,i-1)+
    ∑tj(j=0->i-1)w(i+1)+
    (∑tj(j=0->i-1)+t(i+1))wi+
    ∑tj(j=0->i+1)∑wj(j=i+2->n)+
    F(i+2,n)
∑tj(j=0->i-1)wi+(∑tj(j=0->i-1)+ti)w(i+1)<=
∑tj(j=0->i-1)w(i+1)+(∑tj(j=0->i-1)+t(i+1))wi
tiw(i+1)<=t(i+1)wi

对于任意0<i<n,
t(i-1)wi<=tiw(i-1)          ①
tiw(i+1)<=t(i+1)wi         ②
(各元素皆为自然数)
①式左右各乘t(i+1)w(i+1),即
t(i-1)w(i+1)*t(i+1)wi<=tiw(i+1)*t(i+1)w(i-1)
由②可得
t(i-1)w(i+1)<=t(i+1)w(i-1)
由此可得序列中任意0<=a<b<=n
tawb<=tbwa 

Please login to reply.