Mochila (con división)

📖

Este algoritmo resuelve el siguiente problema:

Tenemos una mochila la cual tiene una capacidad limitada en la cual queremos meter maximizar el valor del contenido de la mochila. Los elementos que podemos meter en esta tiene un beneficio y un perjuicio (habitualmente un peso).

Existen dos variantes de este problema:

Elementos fraccionables → Los elementos de la mochila se pueden partir, obteniendo así solo la parte proporcional del beneficio del objeto respecto de la proporción de este que ha sido introducida a la mochila

Elementos indivisibles → Los elementos solo se pueden meter a la mochila si caben enteros

ℹ️

Descripción del algoritmo

Calcular el ratio entre el beneficio y el peso de los elemetos

Ordenar los elementos según el ratio

Escoger cada vez el elemento con mayor ratio hasta que nos quedemos sin espacio en la mochila.

Si el problema permite partir elementos, fraccionaremos el beneficio del último elemento
Si no, pararemos aquí con el espacio que sobre

🧠 Complejidad → $O(n·\log n)$

🧠

Si la el tamaño de la mochila es muy pequeño comparado con el tamaño de el array de datos, es posible que no valga la pena ordenar

#########################################
# Knapsack greedy algorithm (iterative) #
#########################################


def select_best(data, candidates):
    """
    Choose the best element from the candidates list based on a ratio criteria

    - The data is a tuple (values, weights)
    - The candidates list is a set of indexes {0, 1, 3, ...}
    """
    
    best = 0                                        # Stores the index of the best item in the candidates list
    best_value = 0                                  # Stores the value of the index selected as the currently best item
    
    # Select the best candidate based on the ratio profit/weight
    for c in candidates:
        ratio = data[0][c] / data[1][c]             # Calculate the profit/weight ratio

        # Found a better candidate
        if ratio > best_value:                      # If we find a better candidate, replace the old one
            best = c                                # Update the index of the best item
            best_value = ratio                      # Update the value of the best item
            
    return best


def greedy_knapsack(vals, weights, max_w):
    """
    Greedy algorithm to solve the knapsack problem
    """
    
    n = len(vals)                                   # Number of items available in the knapsack
    candidates = set(range(n))                      # Set of items as candidates to be the next item in the knapsack
    sol = [0] * n                                   # Array containing the proportion of the item is already in the knapsack (0 means not in the knapsack)
    
    # While we have candidates and remaining weight
    while candidates and max_w > 0:
        best = select_best((vals, weights), candidates)  # Select the best candidate
        candidates.remove(best)                     # Remove the best candidate from the set
        
        # If the best candidate fits complete in the knapsack
        if weights[best] <= max_w:
            sol[best] = 1.0                         # Add the item to the solution as it fitted fully into the knapsack (we use floats to state that the solution is made out of floats)
            max_w -= weights[best]                  # Decrease the remaining weight
        # If the best candidate does not fit complete in the knapsack, we add a fraction
        else:
            sol[best] = max_w / weights[best]       # Calculate the proportion of the item that fits into the remaining space in the knapsack
            max_w = 0                               # Hard-code the value of `0` as the remaining weight value to avoid unexpected behaviour of the operation `max_w > 0`

    return sol


#####################################################################

if __name__ == "__name__":
    values = [20, 30, 66, 40, 60]
    weight = [10, 20, 30, 40, 50]
    maxWeight = 100

    solution = greedy_knapsack(values, weight, maxWeight)
    print(solution)