使用遞歸性的線性分區

Question

我知道有類似的問題，但我無法使用它們修改我的代碼。

想象一下，我們有一些工作要做這種成本的時間n = [8,6,7,2,1,4]，和3名工人來做。所以如果我們想要計算分區的最佳方式，我們可以評估所有的選項（這是我想用遞歸函數做的）。這將是所有選項：

1- 1st worker:[8]; 2nd worker:[6]; 3rd worker:[7,2,1,4] --> Cost=max(8, 6 , 7+2+1+4=14)=14 
2- 1:[8]; 2:[6,7]; 3:[2,1,4] --> Cost=max(8,13,7)=13 <------ best 
3- 1:[8,6]; 2:[7]; 3:[2,1,4] --> Cost=max(14,7,7)=14 
4- 1:[8]; 2:[6,7,2]; 3:[1,4] --> Cost=max(8,15,5)=15 
5- 1:[8,6]; 2:[7,2]; 3:[1,4] --> Cost=max(14,9,5)=14 
6- 1:[8,6,7]; 2:[2]; 3:[1,4] --> Cost=max(21,2,5)=21 
7- 1:[8]; 2:[6,7,2,1]; 3:[4] --> Cost=max(8,16,4)=16 
8- 1:[8,6]; 2:[7,2,1]; 3:[4] --> Cost=max(14,10,4)=14 
9- 1:[8,6,7]; 2:[2,1]; 3:[4] --> Cost=max(21,3,4)=21 
10- 1:[8,6,7,2]; 2:[1]; 3:[4] --> Cost=max(23,1,4)=23 

顯然，8/6,7/2,1,4是做它，因爲它是最大pratitions的最小和最佳的選擇。我想在Pyhton中設計一個代碼，它可以計算任何數量的任務和任意數量的工人的最佳分區。

我開始我的代碼是這樣的：

def ib(n,j): #n:list with times,j:number of workers 
    if j==1: 
     return sum(n) #if we have just 1 worker 
    else: 
     for i in range(j-1,len(n)+1): #to explore all the options of the right 
      left=ib(n[0:i],j-1) 
      right=sum(n[i:len(n)]) 
      if right>left: 
       left=right 
ib([8,6,7,2,1,4],3) 

我的想法是找到最後一名工人的時間的總和，然後再貼上功能將留下一個工人少，直到我剛纔1工人。我有一個錯誤，因爲這個功能已經失效了，我得到了左側的None。我不知道如何解決這個問題。

謝謝:)

Answer 1

有太多的瑕疵修復只是一個細節或兩個在你的代碼;我會爲你做你的功課。不過，這裏有一些基本的項目可以幫助你開始。

你得到的結果無，因爲你從你的函數的主枝忽略回報任何內容，其他條款。函數的默認值是無。

此外，您的邏輯無法保留解決方案;它只找到當地最好的。當您重新調用堆棧時，您需要將各種工作負載組成一個列表，保留迄今爲止發現的最佳列表 - 不僅是這個工作人員的最低值。