I have spent countless hours trying to figure this out with no success. The problem I'm trying to solve is finding the paths (i.e. the schedules of tasks) that will provide the most value. See Interval scheduling.
In the chart below, you can see that Task 1 has a value of 5 (the red number), begins at t = 1, and ends at t = 4. Task 2 has a value of 1, begins at t = 3, and ends at t = 5, etc.
You cannot do any tasks that overlap. Meaning if I choose to do task 1, I cannot do task 2, 3, or 5 but I CAN do 4 since it starts directly after 1 finishes.
So the best possible result would be to do task 1, task 4, then task 8. That would be worth 13 points.
I can calculate the maximum value with the code below:
class Tasks:
def __init__(self, task_id, earnings, start_time, end_time):
self.task_id = task_id
self.earnings = earnings
self.start_time = start_time
self.end_time = end_time
self.duration = (end_time - start_time)
def value(n):
n_value = task_list[n-1].earnings
return n_value
def prev(n):
n_start = task_list[n-1].start_time
n_prev = 0
# cycles through list of tasks
for i, task in enumerate(task_list):
# if n_prev has been changed from its initial value of 0
if n_prev > 0:
# finds the latest task endtime that's less than or equal to the start of n
if n_start >= task.end_time > task_list[n_prev-1].end_time:
n_prev = task.task_id
else:
# else, n_prev is 0 and assigns it to the first task that ends before n starts
if n_start >= task.end_time:
n_prev = task.task_id
return n_prev
def get_max(n):
if n == 0:
return 0
# the earnings for doing the task
do_task = value(n) + get_max(prev(n))
# the earnings for not doing the task
dont_do_task = get_max(n-1)
# if doing the task earns more than not doing the task, return do_task
if do_task > dont_do_task:
path.append(n)
return do_task
# otherwise, return the value for not doing the task
else:
return dont_do_task
if __name__ == '__main__':
task_list = [
Tasks(1, 5, 1, 4),
Tasks(2, 1, 3, 5),
Tasks(3, 8, 0, 6),
Tasks(4, 4, 4, 7),
Tasks(5, 6, 3, 8),
Tasks(6, 3, 5, 9),
Tasks(7, 2, 6, 10),
Tasks(8, 4, 8, 11)
]
path = []
get_max(3)
The problem is I can't figure out how to keep track of the paths (or schedules). If I call get_max(8), I want to maintain a list that has 1, 4, and 8 not just the value that they combine to. I can't figure out how to use this function recursively while still tracking the paths that have been explored.
(side note: get_max(0) = 0 so I will just write that as 0)
here's kind of a pseudocode of one example: get_max(3)
get_max(3)
do_task = 8 + 0
dont_task = get_max(2)
makes the recursive call before it can finish:
get_max(2)
do_task = 1 + 0
dont_task = get_max(1)
makes the recursive call before it can finish:
get_max(1)
**do_task = 5 + 0**
dont_do_task = get_max(0)
compares 5 and 0 and returns 5, so now:
get_max(2)
do_task = 1 + get_max(0)
**dont_do_task = 5**
compares 1 and 5 and returns 5, so now:
get_max(3)
**do_task = 8 + get_max(0)**
dont_do_task = 5
compares 8 and 5, 8 is greater
now at this point, I know I want to do task 3. So I would like to add 3 to the list of paths I'm going to take. However if I added something like
if doing path:
path_list.append(n)
then it also would've added 1 to the path list at from when I chose do_task in get_max(1) at the bottom of the recursion, which I don't want. Is there any way to ensure that I'm only adding the relevant paths to the list?
EDIT
For what it's worth, I did come up with a workaround but it's not very elegant, and it depends on calling get_max(n) in sequential order. (I also imported defaultdict from collections to make adding to the list easier)
def calculate():
for i in range(numTasks):
recursive_max(i + 1)
def get_max(n):
if n == 0:
return 0
previous = prev(n)
if previous in path_dict:
do_task = value(n) + value_dict[previous][0]
else:
do_task = value(n) + get_max(previous)
if n-1 in path_dict:
dont_do_task = value_dict[n-1][0]
else:
dont_do_task = get_max(n - 1)
if do_task > dont_do_task:
if n not in path_dict:
if previous > 0:
for path in path_dict[previous]:
path_dict[n].append(path)
path_dict[n].append(n)
value_dict[n].append(do_task)
return do_task
# otherwise, return the value for not doing the task
else:
if n not in path_dict:
for path in path_dict[n-1]:
path_dict[n].append(path)
value_dict[n].append(dont_do_task)
return dont_do_task