经典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)
全部评论

相关推荐

06-26 15:35
武汉大学 运营
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
06-04 09:27
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-26 15:18
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务