python - 使用递归的线性划分

Question

我知道有类似的问题，但我不能使用它们修改我的代码。

想象一下，我们有一些工作需要花费 n=[8,6,7,2,1,4] 的时间来完成，需要 3 个 worker 来完成。因此，如果我们想计算制作分区的最佳方法，我们可以评估所有选项(这就是我想用递归函数做的)。这些将是所有选项:

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 是最好的选择，因为它是最大概率的最小和。我想在 Pyhton 中设计一个代码，它计算任意数量的任务和任意数量的 worker 的最佳分区。

我的代码是这样开始的:

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)

我的想法是找到最后一个 worker 的时间总和，然后再次将函数应用到左边，少一个 worker ，直到我只有 1 个 worker 。我有一个错误，因为功能超出了 for 并且我在左侧得到了 None 。我不知道如何纠正这个。

谢谢你:)

Answer 1

缺陷太多，无法仅修复代码中的一两个细节；我会为你做功课。但是，这里有一些基本项目可以帮助您开始自己的道路。

您得到的结果是None，因为您忽略了从函数的主要分支else 子句返回 任何内容。函数的默认值为无。

此外，您的逻辑无法保留解决方案；它只找到本地最好的。当您重新返回调用堆栈时，您需要将各种工作负载形成一个列表，保留迄今为止找到的最佳列表——而不仅仅是这个工作人员的最低值。