0/1 Knapsack Problem
Tienes n artículos. El artículo i pesa weights[i] y vale values[i]. Tu mochila puede llevar un peso total de como máximo capacity. Cada artículo existe una sola vez, y o bien lo empacas entero o lo dejas atrás. Devuelve el mayor valor total que puedes empacar.
Función
- weightsinteger-array
- el peso de cada elemento
- valuesinteger-array
- el valor de cada elemento
- capacityinteger
- el mayor peso que puede cargar la bolsa
- Devuelveinteger
- el mayor valor total de los artículos cuyos pesos caben en la capacidad
Restricciones
1 ≤ n ≤ 100, donden = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
Ejemplos
- Entrada
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- Salida
- 17
- Explicación
- Los elementos 0 y 2 pesan 4 + 3 = 7 y valen 10 + 7 = 17. Empacar primero el elemento más valioso (peso 5, valor 12) deja espacio solo para el elemento 1, para un total de 16.
- Entrada
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- Salida
- 13
- Explicación
- Los artículos 1 y 2 pesan 4 + 3 = 7 y valen 7 + 6 = 13. El artículo 0 obtiene 2 por unidad de peso, tanto como cualquier otro artículo, pero después de incluirlo, las 2 unidades restantes no alcanzan para nada.
- Entrada
- weights = [6, 8]values = [5, 9]capacity = 5
- Salida
- 0
- Explicación
- Ambos artículos pesan más de 5, así que no cabe nada y la bolsa vacía vale 0.
Para ir más allá
Supongamos que la capacidad puede llegar a 10^9 mientras que los valores suman como máximo 10^4. ¿Por qué indexarías la tabla?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Decide sobre los artículos en orden, empezando por el artículo 0. Tanto si lo incluyes como si lo dejas, te enfrentas a la misma pregunta sobre los artículos que vienen después. ¿Qué número cambia en esa pregunta?
El mejor valor a partir de aquí depende solo de dos números: qué elemento estás mirando y cuánto espacio queda. Con 100 elementos y una capacidad de 1000, hay aproximadamente 10^5 pares de este tipo, así que puedes calcular cada uno una vez y almacenarlo.
Mantén
best[c]para cada capacidadcdesde 0 hastacapacity, todos con valor 0 al principio. Para un elemento de pesowy valorv, recorrecdesdecapacityhacia abajo hastawy conserva el mayor valor entrebest[c]ybest[c-w] + v. Recorrer hacia abajo evita que el elemento se empaquete dos veces.
Solución
Ningún orden voraz funciona: empaquetar primero el artículo más valioso da 16, no 17, en el primer ejemplo. El mejor valor a partir del artículo i depende solo de i y del espacio restante, un número entero de hasta 1000. Una celda de la tabla por cada par da O(n × capacity), y basta con una fila si recorres las capacidades en orden descendente.
Prueba ambas opciones para cada elemento
Correcto, pero no termina con las pruebas más grandes
Intuición
Sea best(i, room) el valor máximo que pueden aportar los elementos desde i en adelante con room unidades libres; después del último elemento, es 0. Omitir el elemento i da best(i+1, room). Empacarlo, cuando weights[i] ≤ room, da values[i] + best(i+1, room-weights[i]). Quédate con el mayor valor. Cada forma de empacar que cabe es una secuencia de decisiones de empacar u omitir, y la recursión las prueba todas.
Cada elemento duplica los caminos. Cuando caben juntos los 100 elementos, como ocurre con un peso de 10 cada uno en una bolsa de 1000, hay 2^100 caminos.
Algoritmo
- Escribe
best(i, room); devuelve 0 cuandoisupera el último elemento. - Asigna
skipabest(i+1, room). - Si
weights[i] > room, devuelveskip. - De lo contrario, devuelve el mayor entre
skipyvalues[i] + best(i+1, room-weights[i]). - Devuelve
best(0, capacity).
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)Completa una tabla por elemento y capacidad
Intuición
La recursión alcanza el mismo par (i, room) por muchos caminos. Hay como máximo 101 × 1001, aproximadamente 10^5, pares, así que calcula cada uno una sola vez.
Sea best[i][c] el mayor valor que los primeros i artículos pueden llevar en una mochila de capacidad c; la fila 0 contiene solo 0. Para el artículo i-1, con peso w y valor v, dejarlo fuera da best[i-1][c] y, si w ≤ c, meterlo da best[i-1][c-w] + v. La fila i solo lee la fila i-1, así que cada artículo entra en una celda como máximo una vez.
En el primer ejemplo, el artículo 2 (peso 3, valor 7) eleva la capacidad 7 a best[2][4] + 7 = 17. El artículo 3 ofrece después solo best[3][2] + 12 = 16, así que la respuesta sigue siendo 17.
Algoritmo
- Crea una tabla de n+1 filas y capacity+1 columnas, todas con valor 0.
- Para cada fila
i, de 1 a n, tomaw = weights[i-1]yv = values[i-1]. - Para cada capacidad
c, establecebest[i][c]enbest[i-1][c]. - Si
w ≤ cybest[i-1][c-w] + ves mayor, guarda ese valor en su lugar. - Devuelve
best[n][capacity].
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]Una fila, capacidades recorridas en orden descendente
Intuición
La fila i solo necesita la fila i-1, así que conserva una fila best[c] y sobrescríbela elemento por elemento. La dirección del recorrido determina si la respuesta es correcta.
Al recorrer c en orden ascendente, best[c-w] puede incluir ya el elemento actual. Un elemento de peso 3 y valor 5 con una capacidad de 6 hace que la capacidad 3 valga 5; después, la capacidad 6 lo lee y pasa a valer 10: dos copias. Al recorrer en orden descendente desde capacity hasta w, la celda que lees está por debajo de la que escribes y se sobrescribe más tarde, así que todavía contiene el valor de la fila anterior.
El recorrido ascendente es el bucle correcto cuando los elementos se pueden tomar en copias ilimitadas. Aquí el tiempo sigue siendo O(n × capacity) y la memoria se reduce a una fila.
Algoritmo
- Crea
bestconcapacity + 1elementos, todos en 0. - Para cada elemento con peso
wy valorv, recorrecdesdecapacityhastaw. - Si
best[c-w] + vsupera abest[c], guárdalo enbest[c]. - Devuelve
best[capacity].
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
Errores comunes y casos límite
- Recorrer las capacidades en orden ascendente en la versión de una sola fila cuenta dos veces un artículo: un artículo de peso 3 y valor 5 en una mochila de capacidad 6 suma 10 en lugar de 5.
- Una fila de
capacityentradas en lugar decapacity + 1. Devolverbest[capacity-1]hace que se pierda cualquier combinación que llene la mochila exactamente, como un artículo de peso 1 en una mochila de capacidad 1. - Inicializar las entradas con menos infinito. No es necesario que la mochila esté llena, así que todas las entradas empiezan en 0; con menos infinito, el tercer ejemplo devuelve menos infinito en lugar de 0.
- Hay que omitir los artículos que pesen más que la mochila. En el tercer ejemplo, un rango cerrado
w...capacitydetiene el programa en Swift, y(w+1):(capacity+1)cuenta hacia atrás en R.
Preguntas frecuentes3
¿Cuál es la complejidad temporal del problema de la mochila 0/1?
La tabla se ejecuta en tiempo O(n × capacity), aproximadamente 10^5 pasos para 100 elementos y una capacidad de 1000, y la versión de una fila usa O(capacity) de memoria. El límite es seudopolinómico: crece con el valor de la capacidad, no con su número de dígitos. El problema general es NP-hard.
¿Por qué no funciona un algoritmo voraz para el problema de la mochila 0/1?
Una regla voraz nunca deshace una elección, ni siquiera cuando el elemento deja espacio que nada llena. Con una capacidad de 7, el elemento de peso 5 y valor 10 empata en la mejor proporción, pero los elementos de peso 4 y 3 juntos valen 13. La estrategia voraz basada en la proporción es óptima solo para la mochila fraccionaria, donde puedes dividir los elementos.
¿Cómo encuentras qué elementos eligió la mochila 0/1?
Conserva la tabla completa y retrocede desde best[n][capacity]. Si best[i][c] es diferente de best[i-1][c], se empaquetó el elemento i-1, así que regístralo y resta su peso a c. De lo contrario, pasa a la fila i-1 con el mismo c.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def knapsack(weights, values, capacity):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
Salida Esperada
17