查找完成可按任意順序完成的操作的最短時間

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)))