如题
在证明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 并非是最优子结构
想请问是我对最优子结构的定义产生误解吗?