《算法设计与分析》课程笔记（代码：动态规划+贪心算法+回溯算法） by 浅若清风cyf

''' - 这里有n门不同的在线课程，按从1到n编号。 - 现有一个数组courses,其中courses[i]=[duration,lastDay,表示第i门课将会持续上duration;天课，并且必须在不晚于lastDay,的时候完成。 - 规定从第1天开始，且不能同时修读两门及两门以上的课程。 - 返回最多可以修读的课程数目。 请设计一个贪心求解算法。 courses=[100,200],[200,1300],[1000,1250],[2000,3200] 答案：3 解释： 这里一共有4门课程，但是你最多可以修3门： 首先，修第1门课，耗费100天，在第100天完成，在第101天开始下门课。 第二，修第3门课，耗费1000天，在第1100天完成，在第1101天开始下门课程。 第三，修第2门课，耗时200天，在第1300天完成。 第4门课现在不能修，因为将会在第3300天完成它，这已经超出了关闭日期。 贪心策略：将courses按照$$lastDay_i$$,从小到大排序，然后遍历courses,假设当前遍历到第i个，前i-1课程所花费的总时间为sum, $$sum+duration_i>lastDay_i$$, 此时我们考虑，如果前i-1个课程中有花费时间大于$$duration_i$$的课程， 那么将其删除替换成$$duration_i$$,一定不会比之前的最后结果差。 理解：排到第i门课程时，若发现在前面的i-1门课安排后无法在第i门课截止时间前修完这门课， 则需要在前面的课程中找比它持续时间长的课，将前面那门课替换成第i门课（第i门课比前面已选的课更省时，更晚结束），得到更优的解 ''' def arrange_courses(courses: list): ''' 求解最大安排课程数量的策略 :param courses: [[duration_day,last_day], ...] :return: ''' courses_sorted = sorted(zip([i for i in range(len(courses))], courses), key=lambda x: x[1][1]) # 按照last day进行排序 print('排序：', courses_sorted) total_duration = 0 choices = [] # 记录选择的课程id for i in range(len(courses_sorted)): ''' 课程id：courses_sorted[i][0] 持续时间：courses_sorted[i][1][0] 截止时间：courses_sorted[i][1][1] ''' # 超出课程截止日期 if total_duration + courses_sorted[i][1][0] > courses_sorted[i][1][1]: # 寻找已选的课程中持续时间比课程i还长的课程，替换为课程i for j in range(len(choices)): if courses[choices[j]][0] > courses_sorted[i][1][0]: choices[j] = courses_sorted[i][0] total_duration = total_duration - courses[choices[j]][0] + courses_sorted[i][1][0] break # 能够在课程截止日期前完成 else: choices.append(courses_sorted[i][0]) # 把课程id加入选择列表 total_duration += courses_sorted[i][1][0] return choices if __name__ == '__main__': courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] print(f'课程：{courses}') choices = arrange_courses(courses) print('课程安排：', '->'.join([f'课程{course_id}' for course_id in choices])) ''' 课程：[[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 排序： [(0, [100, 200]), (2, [1000, 1250]), (1, [200, 1300]), (3, [2000, 3200])] 课程安排： 课程0->课程2->课程1 '''