如题 在证明greedy的时候 往往要证明greedy-choice property和optimal substructure 但是小弟今天在证明scheduling to minimize maximum lateness时 发现optimal substructure会证明不出来 optimal substructure的定义是 每个最优解greedy-choice後剩余的必定是最优子集合 然而这题如果有3个工作分别是a b c a的工作时间是 2 b的工作时间是 10 c的工作时间是 3 而deadline a 是 1 b是6 c 是5 则a->c->b c->a->b 皆是最优结构 maximum lateness 为9 但是 a->c 和 c->a的 maximum lateness 却是1 和 4 c->a 并非是最优子结构 想请问是我对最优子结构的定义产生误解吗? --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.30.32 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1478437818.A.C32.html