Suma mínima de subconjuntos
Publicado por Recursividad (1 intervención) el 19/04/2017 17:28:36
Imaginemos que estos son los tiempos que se tardan en hacer varios trabajos n=[8,6,7,2,1,4], y que tenemos 3 trabajadores. Analicemos todas las opciones para hacer el reparto de trabajos:
1- 1 trabajador:[8]; 2 trabajador:[6]; 3 trabajador:[7,2,1,4] --> Coste=max(8, 6 , 7+2+1+4=14)=14
2- 1:[8]; 2:[6,7]; 3:[2,1,4] --> Coste=max(8,13,7)=13 <------ mejor
3- 1:[8,6]; 2:[7]; 3:[2,1,4] --> Coste=max(14,7,7)=14
4- 1:[8]; 2:[6,7,2]; 3:[1,4] --> Coste=max(8,15,5)=15
5- 1:[8,6]; 2:[7,2]; 3:[1,4] --> Coste=max(14,9,5)=14
6- 1:[8,6,7]; 2:[2]; 3:[1,4] --> Coste=max(21,2,5)=21
7- 1:[8]; 2:[6,7,2,1]; 3:[4] --> Coste=max(8,16,4)=16
8- 1:[8,6]; 2:[7,2,1]; 3:[4] --> Coste=max(14,10,4)=14
9- 1:[8,6,7]; 2:[2,1]; 3:[4] --> Coste=max(21,3,4)=21
10- 1:[8,6,7,2]; 2:[1]; 3:[4] --> Coste=max(23,1,4)=23
Por lo tanto, está claro manera más justa para repartir los trabajos sería 8 / 6,7 / 2,1,4. Ya que en este caso el trabajador que más tarda, tardará 13, por lo que es la mejor opción.
Tenemos que diseñar una función recursiva en Python que resuelva esto para cualquier número de tareas, y cualquier número de trabajadores. La función consistirá en elegir la parte de la derecha que hará el último trabajador y aplicar la función a la parte izquierda con un trabajador menos, hasta que solo nos quede un trabajador. Por ejemplo, siguiendo el ejemplo de arriba:
8,6,7 / 2,1,4
Cuando nuestra parte derecha (trabajador 3), sea 2,1,2 podemos aplicar la función a la parte izquierda entonces la función nos sacará la mejor opción de la parte izquierda.
Así es como he empezado pero no sé cómo continuar ya que en un momento dado la función se sale del for y me devuelve None porque no ha entrado en j==1
Se agradecería cualquier tipo de ayuda. Gracias :)
1- 1 trabajador:[8]; 2 trabajador:[6]; 3 trabajador:[7,2,1,4] --> Coste=max(8, 6 , 7+2+1+4=14)=14
2- 1:[8]; 2:[6,7]; 3:[2,1,4] --> Coste=max(8,13,7)=13 <------ mejor
3- 1:[8,6]; 2:[7]; 3:[2,1,4] --> Coste=max(14,7,7)=14
4- 1:[8]; 2:[6,7,2]; 3:[1,4] --> Coste=max(8,15,5)=15
5- 1:[8,6]; 2:[7,2]; 3:[1,4] --> Coste=max(14,9,5)=14
6- 1:[8,6,7]; 2:[2]; 3:[1,4] --> Coste=max(21,2,5)=21
7- 1:[8]; 2:[6,7,2,1]; 3:[4] --> Coste=max(8,16,4)=16
8- 1:[8,6]; 2:[7,2,1]; 3:[4] --> Coste=max(14,10,4)=14
9- 1:[8,6,7]; 2:[2,1]; 3:[4] --> Coste=max(21,3,4)=21
10- 1:[8,6,7,2]; 2:[1]; 3:[4] --> Coste=max(23,1,4)=23
Por lo tanto, está claro manera más justa para repartir los trabajos sería 8 / 6,7 / 2,1,4. Ya que en este caso el trabajador que más tarda, tardará 13, por lo que es la mejor opción.
Tenemos que diseñar una función recursiva en Python que resuelva esto para cualquier número de tareas, y cualquier número de trabajadores. La función consistirá en elegir la parte de la derecha que hará el último trabajador y aplicar la función a la parte izquierda con un trabajador menos, hasta que solo nos quede un trabajador. Por ejemplo, siguiendo el ejemplo de arriba:
8,6,7 / 2,1,4
Cuando nuestra parte derecha (trabajador 3), sea 2,1,2 podemos aplicar la función a la parte izquierda entonces la función nos sacará la mejor opción de la parte izquierda.
Así es como he empezado pero no sé cómo continuar ya que en un momento dado la función se sale del for y me devuelve None porque no ha entrado en j==1
1
2
3
4
5
6
7
8
9
10
11
12
def fuerza_bruta(n,j): #n:lista de costes de tiempo,j:número de trabajadores
if j==1:
return sum(n) #cuando lleguemos a un trabajador él tendrá que hacer todo el trabajo
else:for i in range(j-1,len(n)): #para ir barajando todas las opciónes de la derecha
izquierda=ib(n[0:i],j-1)
derecha=sum(n[i:len(n)])
if izquierda>derecha:
derecha=izquierdafuerza_bruta([8,6,7,2,1,4],3)
Se agradecería cualquier tipo de ayuda. Gracias :)
Valora esta pregunta
0