algorithm - Finding minimum time to complete actions that can be done in any order -

algorithm - Finding minimum time to complete actions that can be done in any order -

lets given t (<= 20) tasks. each task takes corresponding length of time complete. after completing each task, obtain tool can used on specified tasks finish them s : (0 <= s <= 15) times faster — if task took time t_i, takes time ceil(t_i / s). minimum time takes finish tasks? note can utilize 1 tool @ time each task — cannot switch tools in middle of task nor can utilize multiple tools @ same time.

for instance, have finish 3 tasks.

task #1 takes 5 minutes. upon completing tool can finish task #2 3 times faster , task #3 2 times faster.

task #2 takes 10 minutes. upon completing tool can finish task #1 2 times faster , task #3 5 times faster.

task #3 takes 5 minutes. upon completing tool can finish task #1 2 times faster , task #2 2 times faster.

in example, quickest way proceed first finish task #1, utilize tool task #1 finish task #2 in ceil(10/3) minutes, utilize tool task #2 finish task #3 in ceil(5/5) minutes. leads total of 5 + 4 + 1 = 10 minutes.

one way thought of doing recursion). total time taken :

ceil(curtask/besttool) + min({othertasks})

where othertasks not-yet completed tasks. along way update best possible tool each task.

however, naive brute-force takes long. looked @ trying convert memoized recursion (dp - dynamic programming) not sure values cache.

the other possible way might work create sort of graph , run shortest path algorithm dijkstra's, think creating graph have big of complexity.

what best way approach problem?

dynamic programming, memoize cumulative time, tasks left, , time multipliers each task.

some sample python code (if tools thrown away after each task):

class="lang-python prettyprint-override">from math import ceil tasktimes = {1:5, 2:10, 3:5} tools = {1:(1,3,2), 2:(2,1,5), 3:(2,2,1)} cache= {} def rec(totaltime, tasksleft, multipliers): if len(tasksleft) == 0: homecoming totaltime key = (totaltime, tasksleft, multipliers) if key in cache: homecoming cache[key] t = 10**10 task in tasksleft: newtasksleft = tuple(i in tasksleft if i!=task) curtime = ceil(tasktimes[task] / float(multipliers[task-1])) t = min(t, rec(totaltime+curtime, newtasksleft, tools[task])) cache[key] = int(t) homecoming cache[key] print rec(0, tuple(range(1,len(tools)+1)), tuple([1]*len(tools)))'

if best tools kept on time:

class="lang-python prettyprint-override">from math import ceil tasktimes = {1:5, 2:10, 3:5} tools = {1:(1,3,2), 2:(2,1,5), 3:(2,2,1)} cache= {} def rec(totaltime, tasksleft, multipliers): if len(tasksleft) == 0: homecoming totaltime key = (totaltime, tasksleft, multipliers) if key in cache: homecoming cache[key] t = 10**10 task in tasksleft: newtasksleft = tuple(i in tasksleft if i!=task) newmultipliers = tuple(max(a,b) a,b in zip(tools[task], multipliers)) curtime = ceil(tasktimes[task] / float(multipliers[task-1])) t = min(t, rec(totaltime+curtime, newtasksleft, newmultipliers)) cache[key] = int(t) homecoming cache[key] print rec(0,tuple(range(1,len(tools)+1)),tuple([1]*len(tools)))

algorithm recursion dynamic-programming graph-algorithm