动态规划问题，求高手给出解决思想
Suppose you have one machine and a set of n jobs a1, . . . , an to process on that machine. Each job aj has a processing time tj, a profit pj , and a deadline dj. The machine can process only one job at a time, and job ajmust run uninterruptedly for tj consecutive time units. If job aj is completed by its deadline dj, you receive a profit pj, but if it is completed after itsdeadline, you receive a profit of 0. Give an algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times are integers between 1 and n. What is the running time of your
algorithm?
[解决办法]
有点像0-1背包了，可以如下进行考虑：
（1）按照deadline对任务进行排序，deadline早的排在前面，同时剔除tk > dk的任务（因为这些任务即使第一个做，也不可能在截止日期前完成）,记排序之后的截止日期从前到后为D1,D2,...DN：
0----D1---D2-------------------->DN
（2）分析状态，目标函数是Profit，Profit的因变量有两个：任务和当前时间
假设排序后的任务依次是：Task1,Task2,...Taskn，对应需要的时间分别为Cost1,Cost2,...Costn，对应的收益分别为Pay1,Pay2,...Payn，并用i表示剩下的任务中截止时间最早的任务编号，用currentTime表示当前时间，则可以得出如下状态转移方程：
Profit(i, currentTime) = max(Profit(i+1, currentTime), //不做Taski
Payi + Profit(i+1, currentTime+Costi));//做Taski
从而原题的解为Profit(1, 0)
[解决办法]
不好意思，上面的状态转移还是有点问题，更正一下：
Profit(i, currentTime) = max(
Profit(i+1, currentTime),//不做Taski，或者不能在deadlinei前完成，即currentTime + Costi > deadlinei
Payi + Profit(i+1, currentTime+Costi)//做Taski且有currentTime + Costi <= deadlinei
);
