Difícil · PD

Mochila 0/1

Esta tabla ya la viste: best[c] = la mejor respuesta con capacidad c. Cambio de monedas la rellenaba hacia delante porque cada moneda era ilimitada; aquí cada objeto existe una sola vez, y ese único hecho voltea el bucle interno de adelante hacia atrás. Una dirección de bucle es la diferencia entre alquilar y poseer.

En una frase<code>best[c] = valor máximo con capacidad c</code>; por objeto, recorre c desde W <em>hacia abajo</em> hasta w: <code>best[c] = max(best[c], best[c-w] + v)</code>. Hacia atrás = cada objeto una vez.

El problema

Entrada: La primera línea trae n y W (1 ≤ n ≤ 20, 1 ≤ W ≤ 1000). Luego n líneas: w v, el peso del objeto (1 ≤ w ≤ 1000) y su valor (1 ≤ v ≤ 1000).

Salida: El valor total máximo alcanzable con peso total ≤ W, tomando cada objeto como mucho una vez.

Ejemplos:

Entrada	Salida
`1 6 3 5`	`5`
`3 5 2 3 3 4 4 5`	`7`

El primer ejemplo es el detector de reutilización: un objeto de peso 3 y valor 5 en una mochila de 6. Cogerlo dos veces daría 10 — la respuesta correcta es 5, y solo el bucle hacia atrás la acierta.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Por qué hacia atrás, en una frase

best[c-w] + v debe significar «lo mejor sin este objeto». Barriendo c hacia abajo, cada best[c-w] que lees sigue siendo de la fila del objeto anterior — intacto, así que el objeto no puede contarse dos veces. Barriendo hacia arriba, best[c-w] ya fue actualizado en esta ronda: el objeto se cuela dos veces, y el primer ejemplo (respuesta 10 en vez de 5) lo caza.

Pista 2 — Pon la tabla a cero tú mismo

best es global, y en este motor los arrays globales no se ponen a cero solos (la lección de Multiplicación de matrices). Un bucle: for (c = 0; c <= W; c++) best[c] = 0;. La capacidad vacía legítimamente vale 0 — de ese caso base crece toda la tabla.

Pista 3 — Objetos que no caben

Un objeto más pesado que W es entrada legal y simplemente se salta — el bucle de W hacia abajo hasta w[i] lo hace automáticamente, porque el cuerpo nunca se ejecuta cuando w[i] > W. Resiste la tentación de filtrar la entrada; los propios límites del bucle son el filtro.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    for (int c = 0; c <= W; c++) best[c] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = W; c >= w[i]; c--) {
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }

    cout << best[W] << endl;
    return 0;
}

Voltea el bucle interno hacia adelante y obtienes Cambio de monedas — suministro ilimitado, la misma línea de código con la otra convención. Esa simetría es el árbol genealógico de las mochilas en una imagen: 0/1 aquí, ilimitada allí, y con una dimensión más (unidades por objeto) la acotada. La fuerza bruta 2^n de Generar subconjuntos es el plan B cuando W es astronómico pero n se queda mínimo.

Análisis profundo

Por qué funciona

best[c] = el mejor valor alcanzable con capacidad c usando los objetos ya procesados. El bucle de objetos procesa uno por vez; el bucle de capacidad debe correr hacia atrás para que cada best[c-w] leído pertenezca aún a la fila anterior — «sin este objeto». Hacia atrás es lo que lo hace 0/1; hacia adelante dejaría emparejarse un objeto consigo mismo, que es exactamente la mochila ilimitada (cambio de monedas).

El coste

O(n × W) de tiempo — 20 × 1000 = 20.000 transiciones — y O(W) de espacio. La alternativa (una tabla por subconjunto de objetos) serían 2^20 tablas; el truco rodante 1D es lo que colapsa la dimensión de objetos.

Dónde falla

Recorrer la capacidad hacia adelante reutiliza objetos: el primer ejemplo (un objeto, respuesta 10 en vez de 5) está construido para cazarlo con precisión.
Confiar en un global a cero: este motor no pone arrays a cero; best[c] = 0 para todo c debe ser explícito.
Intercambiar w y v en la entrada o en la transición: best[c-w] usa el peso y el término añadido el valor — un símbolo cambiado invierte el problema en silencio.

Siguiente paso

Voltea el bucle y es Cambio de monedas — la hermana ilimitada. Hacia atrás aquí es 0/1; con unidades por objeto, la acotada. La fuerza bruta de Generar subconjuntos cubre n mínimos con W enorme.

Dos cosas para recordar

Bucle de capacidad hacia atrás = cada objeto una vez; hacia adelante = ilimitado.
Pon la tabla rodante a cero explícitamente; los centinelas INF/0 son los muros de carga de la PD.

🐞 Esta versión falla: ábrela y pruébala

El bucle de capacidad corre hacia adelante — cada objeto se empareja consigo mismo

#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    for (int c = 0; c <= W; c++) best[c] = 0;
    for (int i = 0; i < n; i++) {
        for (int c = w[i]; c <= W; c++) {   // bug: forward loop reuses items
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }
    cout << best[W] << endl;
    return 0;
}