OIA-Wiki

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)

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, \ldots$, y $p=0, 1, 2, \ldots, 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$.

knapsack.cpp

int main(){
    vector<int> peso, valor;
    int P;
    // Se ingresan los pesos y valores, y el peso maximo P
    int n=valor.size();
 
 
    vector< vector<int> > mejorValor(n, vector<int>(P+1, 0));
    for(int p=peso[0]; p<=P; p++){
        mejorValor[0][p]=valor[0];
    }
    for(int i=1; i<n; i++){
        for(int p=0; p<=P; p++){
            mejorValor[i][p]=mejorValor[i-1][p];
            if(peso[i]<=p){
                mejorValor[i][p]=max(mejorValor[i][p], valor[i]+mejorValor[i-1][p-peso[i]]);
            }
        }
    }
    cout<<"El mejor valor que puedo obtener es de "<<mejorValor[n-1][P]<<endl;
}