Se dispone de n (n ≤ 100) objetos y una mochila. El objeto i tiene un peso wi (wi ≤ 100) y un valor vi (vi ≤ 100). La capacidad de la mochila es C (C ≤ 1000). El objetivo es elegir los objetos que se introducen en la mochila para maximizar el valor total. Para cada objeto solo hay dos opciones: ponerlo o no ponerlo. No se puede introducir un objeto varias veces ni tomar una parte de él.

Formato de entrada:

Hay n+1 líneas de entrada:

• La primera línea contiene los valores n y C.
• Las siguientes n líneas contienen dos datos cada una: el peso y el valor del objeto i (1 ≤ i ≤ n).

Formato de salida:

Escribir el valor total máximo que se puede alcanzar.

Ejemplo de entrada:

5 10
2 6
2 3
6 5
5 4
4 6

Ejemplo de salida:

15

La solución clásica con programación dinámica define una tabla dp[i][j] que representa el valor máximo que puede obtenerse usando los priemros i objetos con una capacidad de mochila j.

La relación de recurrencia es:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i])

siempre que j >= peso[i]; en caso contrario, simplemante dp[i][j] = dp[i - 1][j].

Código de ejemplo:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, cap;
    cin >> n >> cap;

    vector<int> peso(n + 1), valor(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> peso[i] >> valor[i];

    // dp[i][j]: valor máximo considerando los primeros i objetos
    // y una capacidad de mochila igual a j
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= cap; ++j) {
            // Opción 1: no incluir el objeto i
            dp[i][j] = dp[i - 1][j];

            // Opción 2: incluirlo si la capacidad lo permite
            if (j >= peso[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - peso[i]] + valor[i]);
            }
        }
    }

    cout << dp[n][cap] << endl;
    return 0;
}

Una implementación alternativa con un arreglo uniidmensional, que reduce el uso de memoria:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, C;
    cin >> N >> C;

    vector<int> w(N + 1), v(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> w[i] >> v[i];

    // dp[j]: valor máximo alcanzable con capacidad j
    vector<int> dp(C + 1, 0);

    for (int i = 1; i <= N; ++i) {
        // Se recorre de derecha a izquierda para no reutilizar el mismo objeto
        for (int j = C; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[C] << endl;
    return 0;
}