Mochila 0-1
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 14 de la Ruta de Aprendizaje.
El problema: elegir objetos sin superar una capacidad
Tenemos una mochila de capacidad 5 y tres objetos. Cada objeto puede usarse cero o una vez; no podemos partirlo ni repetirlo. Queremos maximizar el valor total sin que la suma de pesos supere la capacidad.
| Objeto | Peso | Valor |
|---|---|---|
| A | 2 | 3 |
| B | 3 | 4 |
| C | 4 | 5 |
Elegir el objeto de mayor valor da 5, pero A+B caben juntos y dan 7. Probar todos los subconjuntos funciona, aunque hay 2ⁿ posibilidades. La programación dinámica agrupa elecciones que dejan el mismo problema pendiente.
Descubrir el estado y las dos alternativas
Definamos D(i,c) como el mayor valor que podemos obtener usando solo los primeros i objetos, con capacidad a lo sumo c. Esa definición fija qué objetos quedan disponibles y cuánto peso podemos permitirnos.
Al considerar el objeto i−1, de peso w y valor v, hay dos casos:
- No tomarlo: conservar D(i−1,c).
- Tomarlo, si w≤c: añadir v a D(i−1,c−w).
Elegimos el máximo. Ambas alternativas usan únicamente objetos anteriores, por lo que el actual no puede aparecer dos veces. Sin objetos, D(0,c)=0: siempre podemos elegir el conjunto vacío.
Si el diagrama no cabe, deslízalo horizontalmente.
| Objetos disponibles / capacidad | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Ninguno | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 3 | 3 | 3 | 3 |
| A, B | 0 | 0 | 3 | 4 | 4 | 7 |
| A, B, C | 0 | 0 | 3 | 4 | 5 | 7 |
La celda de capacidad 5 al añadir B compara no tomarlo, valor 3, con tomarlo: el mejor valor previo con capacidad 2 era 3; sumamos 4 y obtenemos 7. La tabla considera todas las elecciones mediante esas dos alternativas exhaustivas.
Guardar solo una fila sin reutilizar el objeto
Cada fila depende solo de la anterior. Podemos usar dp[c] para guardar una
única fila, pero importa en qué orden reemplazamos sus valores.
Al procesar un objeto de peso positivo w, recorremos c de mayor a menor.
Así dp[c−w], a la izquierda, todavía contiene la fila anterior. Con A, peso 2
y valor 3, visitaríamos capacidades 5,4,3,2, dejando 3 en cada una.
Si recorriéramos hacia arriba, actualizaríamos dp[2]=3 y luego usaríamos esa
casilla recién cambiada para poner dp[4]=6: habríamos tomado A dos veces.
El recorrido descendente conserva el significado «cada objeto una sola vez».
Implementación y uso
// dp[c] = mejor valor con peso total A LO SUMO c (no exige llenar la mochila)
// (dp en long long: con valores de hasta 10⁹ la suma se sale de un int)
long long mochila(const vector<int>& peso, const vector<int>& valor, int C) {
vector<long long> dp(C + 1, 0);
for (int i = 0; i < (int)peso.size(); i++)
for (int c = C; c >= peso[i]; c--) // ¡HACIA ATRÁS!
dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]);
return dp[C];
}peso = {2,3,4}, valor = {3,4,5} y mochila(peso,valor,5) devuelve 7.
Los dos vectores deben tener el mismo tamaño. La capacidad debe ser un entero
no negativo y los pesos, enteros no negativos. Con peso cero, cada posición
se actualiza una vez para ese objeto; también se mantiene la restricción 0-1.
Los valores acumulados deben caber en long long.
La frase «capacidad c disponible» del comentario significa presupuesto de peso c, no obligación de llenarlo exactamente. Por eso todas las casillas comienzan en 0. Si se exigiera peso total exactamente c, los pesos todavía inalcanzables tendrían que distinguirse del valor cero, por ejemplo con −∞ y transiciones protegidas.
El tiempo es O(nC) y la memoria O(C). Es una complejidad seudopolinómica: depende del valor numérico de C, no solo de cuántos dígitos ocupa. Una capacidad de 10⁹ hace inviable esta tabla aunque haya pocos objetos.
Qué devuelve y qué requiere otra variante
La función devuelve el mejor valor, no los objetos escogidos. Para reconstruir una elección puedes guardar la tabla completa D y volver desde (n,C): si no tomar el objeto conserva el valor, retrocede sin él; en caso contrario, tómalo y resta su peso. Con empates puede haber varias respuestas correctas.
Si los valores totales son pequeños pero C es enorme, otra formulación guarda el peso mínimo para cada valor alcanzable. Si puedes repetir objetos, cambia el significado del estado y el orden de actualización; no es la misma mochila.
¿Por qué con capacidad 4 la respuesta es 5 y no 6?
El 6 vendría de tomar A dos veces, lo que está prohibido. A+B pesan 5. Entre las elecciones válidas con capacidad 4, tomar solo C da el máximo, 5.
Más práctica en 14 - Programación dinámica I.