hand7.pdf

动态规划：空间换时间。

Weight interval scheduling

对于贪婪算法，如果没有weight， 使用最早时间结束策略就可以了，是最优解，有了weight就不是了。

p(n) 表示和第n个相容的最大的序号的任务。

OPT（n)表示用前n个想找到最大的调度。

现在想找OPT(j+1)和OPT（j）之间的关系。

$OPT（j+1)=OPT(j) \quad 不用j+1\\or\\w_{j+1} + OPT(p(j+1))\quad 用j+1$

递归的思想

SORT在哪里？？

这个答案的解是最后一个，也是最大的。