欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 运维知识 > windows >内容正文

windows

可能是流水调度问题的证明

发布时间:2023/11/16 windows 12 coder
如意编程网 收集整理的这篇文章主要介绍了 可能是流水调度问题的证明 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

之前一直都丢在luogu,现在终于放这了

n个东西需要加工,在A加工的时间是ai, 在B加工的时间是bi,每个东西必须在A加工完后才能在B加工,求最少时间

贪心大体思路:不要让A有空闲时间,B的空闲时间尽量少是最优的

对于贪心思路采用归纳法

对于n = 1的情况,显然最少时间是a1 + b1


对于n = 2的情况:

第一种情况:

假设生产顺序是先(a1, b1)再(a2, b2):

如果b2加工前最后是在等待a2,也就是b1<a2,所以Tmin = a1 + a2 + b2

如果b2加工前最后是在等b1,也就是b1>a2,那么Tmin = a1 + b1 + b2

则容易看出Tmin = a1 + b1 + a2 + b2 - min(b1, a2)

第二种情况:

假设生产顺序是(a2,b2)再(a1,b1),同理可得Tmin = a1 + b1 + a2 + b2 - min(b2, a1)

综上,Tmin = a1 + b1 + a2 + b2 - max(min(b1, a2), min(b2, a1))

则可以得到Johnson不等式:

对于两个待加工的东西x, y,排序

min(x1, y2) < min(x2, y1)

会使得最终答案最优

其实就是,对于所有待加工的东西所花时间(a, b)分成p1类别a <= b和p2类别a > b,对于p1按a递增排序,对于p2按b递减排序,先执行第一种,再执行p2种,得到的答案一定最优

Johnson不等式和这个贪心思路为什么得到的顺序一定相同呢?

对于(a1, b1)和(a2, b2),假设a1 <= b1属于p1类别,a2 > b2属于第二类别

因为Johnson不等式有min(a1, b2) < min(a2, b1),无论左边的是a1小还是b2小,都一定小于右边的min(a2, b1),所以能够得到上面的思路


总结

以上是如意编程网为你收集整理的可能是流水调度问题的证明的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。