经典BP代码

题目说明：
不同的任务有不同的奖励，但同一时间只能执行一个任务，一旦任务开始直到结束不能再开始其他任务。
举例：
任务1的开始时间为1，结束时间为4，执行任务的奖励为5.

问题：
在8个任务中可以获得的最大奖励是多少？

class task():
    def __init__(self,s_time,e_time,value):
        self.start_time = s_time
        self.end_time = e_time
        self.value = value
def get_pre(tasks):
    end_times = [t.end_time for t in tasks]
    pre = [0 for _ in range(len(tasks))]
    for i in range(len(tasks)):
        for j in range(len(end_times)):
            if tasks[i].start_time < end_times[j]:
                pre[i] = j
                break
    print('pre: ', pre)
    return pre

def max_value(tasks,pre):
    opt = [0 for _ in range(len(tasks)+1)]
    opt[0] = 0
    opt[1] = 5
    for i in range(1,len(tasks)+1):
        opt[i] = max(opt[i-1],opt[pre[i-1]]+tasks[i-1].value)
    print(opt)

if __name__ == '__main__':
    data = [[1, 4, 5], [3, 5, 1], [0, 6, 8], [4, 7, 4], [3, 8, 6], [5, 9, 3], [6, 10, 2], [8, 11, 4]]
    tasks = []
    for i in range(len(data)):
        tasks.append(task(data[i][0], data[i][1], data[i][2]))
    pre = get_pre(tasks)
    max_value(tasks,pre)