Algoritmia - Necesito ayuda con un problema de algortimia

 
Vista:

Necesito ayuda con un problema de algortimia

Publicado por Robertone (1 intervención) el 08/09/2005 20:02:55
Hola, a ver si alguien me puede ayudar con un problema de algoritmia que me han propuesto y no soy capaz de sacar. Si alguien me lo pudiera resolver. Es el siguiente:

PROBLEMA DE ALGORITMIA

Un determinado almacen tiene una capacidad maxima de almacenamiento de unidades de MaxU (dato).
En un mes j = 1,2,…12=n, el almacen:

- tiene un stock inicial de Sj unidades 0<=Sj<=MaxU
- puede vender un total de unidades Yj unidades a un precio por unidad de Pj (dato) siendo siempre 0<=Yj<=Sj
- Puede comprar Xj unidades, con un coste por cada unidad de compra de Cj (dato), siempre que al sumar el numero de unidades que compra al stock inicial del mes y restarle el numero total de unidades que vende, se cumpla la condicion de que el nuevo stock de unidades (para el siguiente mes) sea mayor o igual que cero y menor o igual que MaxU

Sabiendo que MaxU=20 y el stock inicial en el mes 1 es de S1= 6 unidades, se trata de obtener los valores de Xj e Yj para j=1,2,…12=n, que maximicen el beneficio del almacen que viene dado por la siguiente expresión.

Beneficio = Sumatorio desde j=1 hasta n de (Pj•Yj – Cj•Xj)

Se pide:
Escribir un algoritmo de programación dinamica que resuelva el problema. Para hacerlo:

- escribir la funcion recursiva que resuelva el problema y Estudiar su complejidad.
- Elimine la recursividad, de la funcion recursiva, y decodifique la solucion. Estudiar su complejidad
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Resolución del problema de optimización de almacén con programación dinámica

Publicado por Alejandro (307 intervenciones) el 05/03/2024 20:08:36
Robertone, vamos a abordar este problema paso a paso. Primero, definiremos la función recursiva y luego eliminaremos la recursividad.

Función recursiva:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def beneficio_maximo(j, stock, MaxU, S, P, C, memo):
    if j == 0:
        return 0
 
    if memo[j][stock] != -1:
        return memo[j][stock]
 
    max_beneficio = 0
 
    # No comprar ni vender en el mes actual
    max_beneficio = beneficio_maximo(j - 1, stock, MaxU, S, P, C, memo)
 
    # Intentar vender Yj unidades
    for y in range(min(stock, S[j]) + 1):
        max_beneficio = max(max_beneficio, P[j] * y - C[j] * max(0, stock + Xj - Yj - MaxU))
 
    memo[j][stock] = max_beneficio
    return max_beneficio
 
# Inicialización y llamada inicial
n = 12
MaxU = 20
S = [0, 6, ...]  # Incluir los valores de stock para los meses 1 a 12
P = [0, P1, ...]  # Incluir los valores de precio por unidad para los meses 1 a 12
C = [0, C1, ...]  # Incluir los valores de costo por unidad para los meses 1 a 12
memo = [[-1] * (MaxU + 1) for _ in range(n + 1)]
 
resultado = beneficio_maximo(n, S[n], MaxU, S, P, C, memo)
print("Beneficio máximo:", resultado)

Complejidad de la función recursiva:



La complejidad de esta función recursiva es exponencial en la entrada, ya que en cada llamada recursiva, estamos explorando todas las posibles combinaciones de comprar y vender unidades para cada mes.

Eliminación de la recursividad:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def beneficio_maximo_iterativo(n, MaxU, S, P, C):
    dp = [[0] * (MaxU + 1) for _ in range(n + 1)]
 
    for j in range(1, n + 1):
        for stock in range(MaxU + 1):
            dp[j][stock] = dp[j - 1][stock]  # No comprar ni vender en el mes actual
 
            # Intentar vender Yj unidades
            for y in range(min(stock, S[j]) + 1):
                dp[j][stock] = max(dp[j][stock], dp[j - 1][stock + Xj - Yj - MaxU] + P[j] * y - C[j] * max(0, stock + Xj - Yj - MaxU))
 
    return dp[n][S[n]]
 
# Llamada a la función iterativa
resultado_iterativo = beneficio_maximo_iterativo(n, MaxU, S, P, C)
print("Beneficio máximo (iterativo):", resultado_iterativo)

Complejidad de la función iterativa:



La complejidad de la versión iterativa es cuadrática en la entrada, ya que estamos utilizando dos bucles anidados para explorar todas las combinaciones posibles.

Ambos enfoques proporcionarán el mismo resultado, pero la versión iterativa es más eficiente y preferible en términos de complejidad temporal.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar