查找完成可按任意顺序完成的操作的最短时间

Question

假设您得到T（< = 20）个任务。每项任务都需要相应的时间才能完成。完成 每个任务后，您可以获得一个可在指定任务来 完成他们s工具：更快（0 < = S < = 15）次 - 如果一个任务之前需要时间t_i， 现在需要时间ceil(t_i/s)。 完成所有任务所需的最短时间是多少？请注意，每次任务只能使用一个工具 - 不能在任务中间切换工具，也不能同时使用多个工具。

---

例如，假设你必须完成3个任务。

任务＃1需要5分钟。一旦完成，你将得到一个工具，可以让 以两倍的速度完成任务＃2三倍，任务＃3以两倍的速度完成。

任务＃2需要10分钟。一旦完成，你将得到一个工具，可以使 完成任务＃1两倍，任务＃3快五倍。

任务＃3需要5分钟。完成后，您将获得一个工具，可以使 以两倍的速度完成任务＃1，并且以两倍的速度完成任务＃2。

---

在这个例子中，进行的最快的方法是第一个完整的任务＃1，使用来自任务＃1的工具来完成任务＃2在小区（10/3）分钟，然后使用来自任务＃2的工具完成 小时（5/5）分钟内的任务＃3。这导致总共5 + 4 + 1 = 10分钟。我想这样做的

一个办法是递归）。总共花费的时间为：

ceil(curTask/bestTool) + min({otherTasks}) 

其中otherTasks是尚未完成的任务。在此过程中，您会为每项任务更新最佳工具。

然而，这种幼稚的蛮力显然需要很长时间。我着眼于试图将其转换为记忆递归（DP - 动态编程），但我不确定要缓存哪些值。

可能工作的其他可能的方式是创建某种图形和运行像Dijkstra的最短路径算法，但我认为只是创造图形本身会有太大的复杂性。

解决此问题的最佳方法是什么？

Answer 1

动态规划，通过累计时间memoize的，剩下的任务和时间乘数为每个任务。

一些示例Python代码（如工具每个任务后扔掉）：

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: 
     return totalTime 

    key = (totalTime, tasksLeft, multipliers) 
    if key in cache: return cache[key] 

    t = 10**10 
    for task in tasksLeft: 
     newTasksLeft = tuple(i for 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) 
    return cache[key] 


print rec(0, tuple(range(1,len(tools)+1)), tuple([1]*len(tools)))' 

如果最好的工具保持一段时间：

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: 
     return totalTime 

    key = (totalTime, tasksLeft, multipliers) 
    if key in cache: return cache[key] 

    t = 10**10 
    for task in tasksLeft: 
     newTasksLeft = tuple(i for i in tasksLeft if i!=task) 
     newMultipliers = tuple(max(a,b) for 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) 
    return cache[key] 


print rec(0,tuple(range(1,len(tools)+1)),tuple([1]*len(tools)))