Partition linéaire utilisant la récursivité

Question

Je sais qu'il y a des questions similaires, mais je ne peux pas modifier mon code en les utilisant. Imaginez que nous ayons quelques travaux à faire avec ce coût de fois n = [8,6,7,2,1,4], et 3 travailleurs pour les faire. Donc, si nous voulons calculer la meilleure façon de faire la partition, nous pouvons évaluer toutes les options (ce que je veux faire avec la fonction récursive). Ceux-ci seraient toutes les options:

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 

Il est clair que 8/6,7/2,1,4 est la meilleure option pour le faire car il est la somme minimum du maximum de pratitions. Je veux concevoir un code en Pyhton qui calcule la meilleure partition avec n'importe quel nombre de tâches et n'importe quel nombre de travailleurs.

J'ai commencé mon code de cette façon:

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) 

Mon idée est de trouver la somme des temps du dernier travailleur et d'appliquer à nouveau la fonction vers la gauche avec un travailleur moins jusqu'à ce que je viens de 1 ouvrier. J'ai une erreur parce que la fuction sort de la pour et je reçois un None pour le côté gauche. Je ne sais pas comment corriger cela.

Merci :)

Answer 1

Il y a trop de défauts pour corriger un détail ou deux dans votre code; Je ferais tes devoirs pour toi. Cependant, voici quelques éléments de base pour vous lancer sur votre chemin.

Vous obtenez Aucun pour le résultat parce que vous avez omis de retour quoi que ce soit de la branche principale de votre fonction, l'autre clause. La valeur par défaut d'une fonction est Aucun.

En outre, votre logique ne parvient pas à conserver la solution; il ne trouve que le meilleur local. Au fur et à mesure que vous renouvelez la pile d'appels, vous devez former les différentes charges de travail dans une liste, conserver la meilleure liste trouvée jusqu'à présent - pas simplement la valeur la plus basse pour ce travailleur.