Fractional Knapsack

Q: ¿Cuál es la complejidad temporal del problema de la mochila fraccionaria?

Ordenar los elementos por valor por peso cuesta O(n log n) y el llenado requiere una sola pasada, así que el total es O(n log n) con O(n) de espacio para el orden. Buscar el elemento más denso en cada ronda cuesta O(n²) .

Q: ¿Cómo se resuelve la mochila fraccionaria sin números de punto flotante?

Con pesos positivos, a / b > c / d es la misma prueba que a × d > c × b , así que compara las densidades multiplicando en cruz. El mejor valor es un número entero más una fracción, values[i] × room / weights[i] para el elemento fraccionado, así que una división entera da exactamente la respuesta redondeada hacia abajo.

MedioVoraz Ordenación

+10

Tienes n artículos. El artículo i vale values[i] y pesa weights[i]. Tu bolsa puede contener un peso total de como máximo capacity, y puedes llevar cualquier parte de un artículo: una parte del artículo i que pese w vale values[i] × w / weights[i].

Escribe una función llamada fractionalKnapsack que devuelva el valor total más alto que puede llevar la bolsa, redondeado hacia abajo al número entero más cercano.

Función

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: el valor de cada elemento
weightsinteger-array: el peso de cada artículo
capacityinteger: el peso máximo que puede soportar la bolsa
Devuelveinteger: el valor total más grande que cabe en la bolsa, redondeado hacia abajo

Restricciones

1 ≤ n ≤ 5000, donde n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Ejemplos

Entrada: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Salida: 151
Explicación: Por unidad de peso, los artículos valen 5, 3, 6 y 2.5. Los artículos 2 y 0 se incluyen enteros por 70, y quedan 27 de capacidad; 27 de las 30 unidades del artículo 1 añaden 81, para un total de 151.

Entrada: values = [10, 7]weights = [4, 3]capacity = 5
Salida: 12
Explicación: El artículo 0 vale 2,5 por unidad y el artículo 1 alrededor de 2,33, así que el artículo 0 se incluye entero por 10. Una de las 3 unidades del artículo 1 añade 7 / 3, y 12 y un tercio se redondea hacia abajo a 12.

Para ir más allá

¿Puedes encontrar la respuesta en tiempo O(n), sin ordenar todos los elementos?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Como puedes cortar los artículos, el problema es voraz, a diferencia del problema de la mochila 0/1: cada unidad de peso debe provenir del artículo que tenga el mayor valor por unidad restante. Ordénalos según esa densidad y llena la mochila en ese orden. Compara las densidades multiplicando en cruz y redondea hacia abajo solo el artículo que cortes, para que nunca se almacenen fracciones.

Elige el artículo más denso en cada ronda

Correcto, pero no termina con las pruebas más grandes

Intuición

Llena la mochila empezando por el elemento más denso: tómalo entero si cabe; si no, toma la parte que llena la mochila y detente. Encuentra el elemento sin usar más denso recorriéndolos todos y comparando values[i] × weights[j] con values[j] × weights[i] en lugar de dividir. Con pesos positivos, es la misma comprobación, y ambos productos se mantienen en 10^8 o menos.

Empezar por el más denso es lo mejor: si una carga contiene cierto peso de un elemento menos denso mientras un elemento más denso no se ha incluido por completo, intercambiar ese peso por el elemento más denso no puede reducir el valor. Sigue intercambiando y llegarás a la carga ordenada de más densa a menos densa.

Hasta n rondas recorren cada una los elementos sin usar: unas n²/2 = 12.5 millones de comparaciones para n = 5000.

Algoritmo

Marca cada elemento como no usado y establece room = capacity y total = 0.
Mientras haya espacio, busca entre los elementos no usados el de mayor densidad, comparando las densidades mediante multiplicación cruzada.
Si no quedan elementos, detente. De lo contrario, marca ese elemento como usado.
Si cabe, suma su valor a total y resta su peso de room. Si no cabe, suma values[i] × room / weights[i] con división entera y detente.
Devuelve total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Ordenar por valor por peso

Intuición

El recorrido vuelve a encontrar una y otra vez el artículo de mayor densidad, pero el orden nunca cambia entre rondas. Ordena los artículos una sola vez, de mayor a menor densidad, con la misma comparación mediante productos cruzados. Los artículos con la misma densidad pueden ir en cualquier orden, ya que valen lo mismo por unidad.

Toma los artículos enteros mientras quepan. El primero que no quepa es el único que fraccionas: añade values[i] × room / weights[i], y la división entera redondea ese valor hacia abajo. Todo lo anterior es un número entero, así que redondear este único término da la respuesta exacta. La ordenación cuesta O(n log n) y el recorrido O(n).

Algoritmo

Crea una lista de los índices de los elementos y ordénala del más denso al menos denso usando la comparación con productos cruzados.
Establece room = capacity y total = 0.
Para cada elemento en ese orden, si weights[i] ≤ room, suma su valor y réstale su peso a room.
De lo contrario, suma values[i] × room / weights[i] con división entera y detente.
Devuelve total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Errores comunes y casos límite

Ordenar solo por valor o por peso. En el primer ejemplo, el artículo que vale 90 ocupa el tercer lugar por densidad; si se toma primero, queda espacio para la mitad del artículo que vale 50, lo que da 115 en lugar de 151.
Dividir antes de multiplicar. Con un valor de 13, un peso de 7 y un espacio de 3, 13 / 7 * 3 en aritmética entera da 3, mientras que 13 * 3 / 7 da el resultado correcto: 5.
Esperar que siempre se corte un artículo. En el tercer ejemplo caben todos los artículos, y la respuesta es la suma de todos los valores: 13.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del problema de la mochila fraccionaria?

Ordenar los elementos por valor por peso cuesta O(n log n) y el llenado requiere una sola pasada, así que el total es O(n log n) con O(n) de espacio para el orden. Buscar el elemento más denso en cada ronda cuesta O(n²).

¿Por qué funciona el algoritmo voraz para la mochila fraccionaria, pero no para la mochila 0/1?

El fraccionamiento te permite intercambiar peso de un elemento menos denso por uno más denso. Sin fraccionamiento, un elemento denso puede dejar un espacio que nada más puede ocupar. Con valores 8, 11, 15, pesos 2, 3, 4 y capacidad 7, elegir primero el más denso toma los pesos 2 y 4 para un valor de 23, mientras que los pesos 3 y 4 dan 26. La versión 0/1 necesita programación dinámica.

¿Cómo se resuelve la mochila fraccionaria sin números de punto flotante?

Con pesos positivos, a / b > c / d es la misma prueba que a × d > c × b, así que compara las densidades multiplicando en cruz. El mejor valor es un número entero más una fracción, values[i] × room / weights[i] para el elemento fraccionado, así que una división entera da exactamente la respuesta redondeada hacia abajo.

def fractionalKnapsack(values, weights, capacity):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Salida Esperada