===== Enunciado ===== Dados $n$ items, cada uno con un peso $p_i$ y un valor $v_i$, y una mochila de peso máximo $P$, cuál es el mayor valor que podemos meter en la mochila sin pasarnos del peso $P$? (El valor que metemos es la suma de los valores de los items que metemos) ===== Solución ===== Recomendamos pensar primero un poco el problema antes de avanzar a ver la solución ... ... Lo que vamos a usar es programación dinámica. Acá, parecido a lo que se dijo en el post de la máxima subsecuencia palindrómica, a priori parece ser muy difícil, ya que hay $2^n$ subconjuntos posibles (cada ítem puede estar o no estar). La programación dinámica, de una manera inteligente, nos permite "mirar todos los subconjuntos" sin mirar de a uno por uno. Sólo miramos los que pueden servir. Estado de la programación dinámica: Vamos a guardar en el par $(i, p)$, el mayor valor que podemos guardar usando hasta el iésimo ítem, sin pasarnos de peso $p$. Supongamos entonces que tenemos $(i, p)$ para todo $i=0, 1, ...$, y $p=0, 1, 2, ..., P$. Qué pasa cuando vamos a mirar el ítem $i+1$? Bueno, si no queremos pasarnos del peso $p$, o usamos el ítem $i+1$, o no. Si no lo usamos, entonces simplemente el mejor valor hasta el ítem $i+1$ sin pasarnos de peso $p$ es el mejor valor con los primeros $i$ items, sin pasarnos de ese paso. Y si lo usamos (para eso $p>=peso[i+1]$ obviamente), entonces vamos a meter el ítem $i+1$, y agarrar el mejor valor que podamos de los ítems anteriores, sin pasarnos ahora de peso $peso[i+1]-p$, para que junto con el ítem $i+1$ no se pasen del peso $p$. Entonces por cada iteración de $i$ y de $p$, tenemos dos valores que mirar, por lo que la complejidad quedará de $n*P$.



int main(){
    vector peso, valor;
    int P;
    // Se ingresan los pesos y valores, y el peso maximo P
    int n=valor.size();
    
    
    vector< vector > mejorValor(n, vector(P+1, 0));
    for(int p=peso[0]; p<=P; p++){
        mejorValor[0][p]=valor[0];
    }
    for(int i=1; i