如題
在證明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 並非是最優子結構
想請問是我對最優子結構的定義產生誤解嗎?