O problema da mochila 0/1 é um clássico da programação dinâmica, onde temos n itens, e cada um pode ser selecionado no máximo uma vez. A abordagem ingênua de busca exaustiva teria complexidade O(2n), mas a programação dinâmica reduz significativamente o custo computacional.

Implementação Base

O código a seguir mostra a versão bidimensional do algoritmo, onde f[i][j] representa o valor máximo obtido considerando os primeiros i itens com capacidade j:

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

const int MAX = 1005;
int volumes[MAX], values[MAX], dp[MAX][MAX];

int main() {
    int n, capacity;
    cin >> n >> capacity;
    for (int i = 1; i <= n; i++) 
        cin >> volumes[i] >> values[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < volumes[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - volumes[i]] + values[i]);
        }
    }
    cout << dp[n][capacity] << endl;
    return 0;
}

Observamos que apenas a linha anterior da matriz é necessária para o cálculo atual. Isso permite a otimização para um array unidimensional, desde que iteremos a capacidade em ordem decrescente para evitar reutilizar valores já atualizados na mesma iteração:

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

const int N = 1010;
int dp[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; j--)
            dp[j] = max(dp[j], dp[j - v] + w);
    }
    cout << dp[m] << endl;
    return 0;
}

Problema de Combinação de Números

Dado um conjunto de n números, queremos contar quantas maneiras de selecionar alguns deles cuja soma seja exatamente m. Definimos f[i][j] como o número de combinações usando os primeiros i números para obter soma j:

#include <iostream>
using namespace std;

const int N = 110, M = 10010;
int dp[N][M], values[N];

int main() {
    int n, target;
    scanf("%d%d", &n, &target);
    for (int i = 1; i <= n; i++) cin >> values[i];
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= values[i])
                dp[i][j] += dp[i-1][j - values[i]];
        }
    }
    cout << dp[n][target] << endl;
    return 0;
}

Novamente, podemos otimizar o espaço usando um array unidimensional com iteração reversa:

#include <iostream>
using namespace std;

const int N = 110, M = 10010;
int dp[M];

int main() {
    int n, target;
    scanf("%d%d", &n, &target);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = target; j >= x; j--)
            dp[j] += dp[j - x];
    }
    cout << dp[target] << endl;
    return 0;
}

Problema Estendido: Agrupamento de Bolas

Temos n tipos de bolas, cada um com uma quantidade específica. Cada tipo pode ser selecionado ou não, totalizando 2n possibilidades. O valor de cada seleção é definido como o número mínimo de grupos (cada grupo com capacdiade 2) necessários para alocar todas as bolas selecionadas, sem repetir cores no mesmo grupo.

Para uma seleção com soma total sum e quantidade máxima de um tipo mx, o valor é dado por max(ceil(sum/2), mx). Para percorrer todas as combinações sem repetição, ordenamos os valores crsecentemente e fixamos um elemento a[i] como o maior da seleção:

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
const int MOD = 998244353;
long long dp[N][N];
int balls[N];

void solve() {
    dp[0][0] = 1;
    int n, total = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &balls[i]);
        total += balls[i];
    }
    sort(balls + 1, balls + n + 1);
    
    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= total; j++) {
            if ((j + 1 + balls[i]) / 2 >= balls[i])
                answer = (answer + (j + balls[i] + 1LL) / 2 * dp[i-1][j]) % MOD;
            else
                answer = (answer + 1LL * balls[i] * dp[i-1][j]) % MOD;
            dp[i][j] = dp[i-1][j];
            if (j >= balls[i])
                dp[i][j] = (dp[i][j] + dp[i-1][j - balls[i]]) % MOD;
        }
    }
    cout << answer << endl;
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}