práctica 2 goku

#Athenea Beltrán y Daniel Bedialauneta
def suma_costes(c):
    P=[c[0]]
    for i in range(1,len(c)):
        P.append(P[-1]+c[i])
    return P

# n: índice de la última tarea considerada
# k: índice del último agente considerado (k se indexa desde 0)
def fuerza_bruta(n,k,c,P):
    if n==k:
        return max(c[0:n+1]),[i for i in range(n+1)]
    elif k==0:
        return P[n],[n]
    else:
        minimo=None
        for i in range(k,n+1):
            c_fb, p_fb = fuerza_bruta(i-1,k-1,c,P)
            if c_fb < P[n]-P[i-1]:
                c_fb = P[n]-P[i-1]
            if minimo==None or c_fb < minimo:
                minimo=c_fb
                arg_min = p_fb + [n]
        return minimo, arg_min


def fuerza_dinamica(n,k,c,P):
    #Inicialización de F y G. Solo inicializo para las posiciones 00,10 y 11.
    #aunque podría hacerlo para toda la primera columna y para toda la diagonal, y así,
    #ahorrar un poco en los if del segundo for
    F=[[0],[0,0]]
    G=[[0],[0,0]]
    F[0][0]=P[0]
    G[0][0]=None
    F[1][0]=P[1]
    G[1][0]=None
    F[1][1]=max(c[:2])
    G[1][1]=0
    #Ahora, para los demás casos de F y G
    for fila in range(2,n+1):
        F.append([None])
        G.append([None])
        for columna in range(min(n,k)+1):
            if columna==0:
                F[fila][columna]=P[fila]
            elif fila==columna:
                F[fila].append(max(c[0:fila+1]))
                G[fila].append(fila-1)
            else:
                minimo=None
                g_minimo=None
                for i in range(columna-1,fila): # i va de columna-1 hasta fila-1
                    coste_combinacion_parcial=F[i][columna-1]
                    if coste_combinacion_parcial<P[fila]-P[i]:
                        coste_combinacion_parcial=P[fila]-P[i]
                    if minimo==None or coste_combinacion_parcial<minimo:
                        minimo=coste_combinacion_parcial
                        g_minimo=i
                F[fila].append(minimo)
                G[fila].append(g_minimo)
    #Una vez creados F y G, calculo la lista que contiene los índices de dónde acaba cada partición
    particiones=[n]
    indice=n
    for columna in range(k,0,-1):
        particiones.insert(0,G[indice][columna])
        indice=G[indice][columna]
    return F[n][k],particiones




import time
import random
N=10,20,40,80,100
M=2,3,4,5,6,7
print("="*63)
print("TAREAS"," "*4,"AGENTES"," "*4,"TIEMPO RECURSIVO"," "*4,"TIEMPO ITERATIVO"," "*4)
print("="*63)
for tareas in N:
    for agentes in M:
        c=[random.randint(0,50) for i in range(tareas)]
        P=suma_costes(c)
        t1=time.process_time()
        fuerza_bruta(tareas-1,agentes-1,c,P)
        t2=time.process_time()
        fuerza_dinamica(tareas-1,agentes-1,c,P)
        t3=time.process_time()
        print("{0:6}      {1:7}      {2:16}      {3:16}".format(tareas,agentes,t2-t1,t3-t2))
    print("="*63)


"""
Un ejemplo
===============================================================
TAREAS      AGENTES      TIEMPO RECURSIVO      TIEMPO ITERATIVO
===============================================================
    10            2                   0.0                   0.0
    10            3                   0.0                   0.0
    10            4                   0.0                   0.0
    10            5                   0.0                   0.0
    10            6                   0.0                   0.0
    10            7                   0.0                   0.0
===============================================================
    20            2                   0.0                   0.0
    20            3                   0.0                   0.0
    20            4                   0.0                   0.0
    20            5                   0.0                   0.0
    20            6              0.015625                   0.0
    20            7               0.03125                   0.0
===============================================================
    40            2                   0.0                   0.0
    40            3                   0.0                   0.0
    40            4                   0.0                   0.0
    40            5                0.0625                   0.0
    40            6                   0.5                   0.0
    40            7                2.6875                   0.0
===============================================================
    80            2                   0.0                   0.0
    80            3              0.015625                   0.0
    80            4              0.046875                   0.0
    80            5               1.03125                   0.0
    80            6               15.4375                   0.0
    80            7             196.84375                   0.0
===============================================================
   100            2                   0.0                   0.0
   100            3                   0.0                   0.0
   100            4              0.109375                   0.0
   100            5               2.40625              0.015625
   100            6             46.890625                   0.0
   100            7            752.796875              0.015625
===============================================================
"""