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.

ObjetoPesoValor
A23
B34
C45

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.

Añadir B: peso 3, valor 4Antes000132333435Después0001324344753 + 4 = 7La dependencia viene de la fila anterior, sin reutilizar B

Si el diagrama no cabe, deslízalo horizontalmente.

Objetos disponibles / capacidad012345
Ninguno000000
A003333
A, B003447
A, B, C003457

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.

Más práctica en 14 - Programación dinámica I.