※ 引述《pangfeng (P老师)》之铭言： : 一台印刷机, 一台装订机, n本书. : 第i本书印刷需pi时间, 装订需bi时间. : 每一本书须先印刷, 再装订. : 问如何排列印刷装订顺序, 以最短时间完成n本书? <Reformulate the problem> Given any optimal schedule, if the optimal time it gives is T = \sum_i(bi)+t, we can always pushing all the binding jobs to start as late as possible, which is, the first binding job starts at time t. So the problem of finding an optimal schedule is to find a schedule that minimize t. <Algorithm: Greedy Algorithm> float t, T, p; int i; 1. Initialize: t = p1; T = p1 + b1; p = p1; Put the first book into schedule; 2. for book i, p = p+pi; if we schedule it in the front, => t = t - min(t, bi) + pi; if we schedule it in the back{ if (p > T) => t = t + (p - T); else, t remains the same; } comare the t in the above cases, choose the schedule giving minimal q, Update T accordingly; 3. repeat 2. until all the books are scheduled. This will give an optimal schedule that takes T. <Proof Note> (well, it is not a formal/complete proof) 1. Noted that in the second step, insert the book between the schduled books won't give a better schedule than insert in the front, because it for sure delayed the books behind but it can't untilize the empty time slots in binding machine before it. --

※ 发信站: 批踢踢兔(ptt2.cc) ◆ From: 68.181.255.120