正月点灯笼-计划任务代码实现含选择路径打印（Python3）
有8个任务及对应的薪酬，求最大报酬及其中一条选择路径？
题目及解析见 B站-up正月点灯笼-动态规划 (第1讲)
Python3
def findPrev(i):
"""查找prev"""
for j in range(i - 1, 0, -1):
if task[j][1] <= task[i][0]:
prev[i] = j
return
prev[i] = 0
# 1.便于编号，数组首位用0占位
task = [(0, 0), (1, 4), (3, 5), (0, 6), (4, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
v = [0, 5, 1, 8, 4, 6, 3, 2, 4]
k = len(task)
# 2.构造prev数组（值与索引映射自带关系）
prev = [0] * k
for i in range(k - 1, 0, -1):
findPrev(i)
# print(prev)
tail = [0] # 用于收集路径尾部
path = [] # path收集路径
# 3.动态规划
OPT = [0] * k # 用0初始化OPT数组
for i in range(1, k):
selected = OPT[prev[i]] + v[i]
unselected = OPT[i - 1]
OPT[i] = max(selected, unselected) # 转态转移方程
# 4.路径收集
# (1)收集路径尾部到tail
if max(selected, unselected) == selected:
tail.append(i)
else:
tail.append(tail[-1])
# (2)收集路径到path,路径需要翻转
tem = [] # 用于临时收集倒序的路径
tem.append(tail[i])
j = tem[-1]
while tail[prev[j]] != 0:
tem.append(tail[prev[j]])
j = tem[-1]
path.append(tem[::-1]) # 路径反转后追加到path
# print(OPT)
print(OPT[-1])
# print(path)
print(path[-1])
题目来源：B站-up正月点灯笼-动态规划 (第1讲)
#代码实现#
金山WPS公司福利 286人发布
投递小米集团等公司10个岗位 >