A Programação Dinâmica (DP) é uma técnica fundamentada na decomposição de problemas complexos em subproblemas menores. O objetivo é construir a solução do problema principal a partir dos resultados ótimos desses subproblemas, evitando recomputações desnecessárias.

1. O Problema da Mochila 0/1 (0/1 Knapsack)

Neste cenário, temos $m$ itens, cada um com um peso peso[i] e um valor valor[i]. O objetivo é preencher uma mochila com capacidade máxima $V$ de forma que o valor total seja maximizado, respeitando o limite de peso e a regra de que cada item pode ser escolhido apenas uma vez (ou 0 ou 1).

A abordagem gananciosa (Greedy), que escolhe sempre o item de maior valor ou melhor densidade, nem sempre funciona. Por exemplo, se a capacidade é 4 e temos itens de (Peso 1, Valor 2) e (Peso 4, Valor 7), a lógica gananciosa pegaria o de valor 7, mas dependendo da dispoinbilidade de outros itens, combinações de itens menores poderiam superar esse valor.

Abordagem Bidimensional

Definimos uma matriz dp[i][j] onde $i$ representa os itens considerados e $j$ a capacidade atual da mochila. Para cada item, temos duas escolhas:

• Não incluir o item: o valor total é o mesmo que o acumulado para o item anterior com a mesma capacidade: dp[i-1][j].
• Incluir o item: o valor é o valor do item atual mais o valor máximo que podíamos carregar com o espaço restente: dp[i-1][j - peso[i]] + valor[i].

A equação de transição de estado é:

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

Exemplo de implementação para o problema clássico de colheita de ervas:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int tempo_total, qtd_ervas;
    cin >> tempo_total >> qtd_ervas;

    vector<int> tempo_coleta(qtd_ervas + 1);
    vector<int> valor_erva(qtd_ervas + 1);
    // Tabela DP: itens x tempo
    vector<vector<int>> matriz_dp(qtd_ervas + 1, vector<int>(tempo_total + 1, 0));

    for (int i = 1; i <= qtd_ervas; i++) {
        cin >> tempo_coleta[i] >> valor_erva[i];
    }

    for (int i = 1; i <= qtd_ervas; i++) {
        for (int j = 1; j <= tempo_total; j++) {
            if (j >= tempo_coleta[i]) {
                matriz_dp[i][j] = max(matriz_dp[i - 1][j], 
                                      matriz_dp[i - 1][j - tempo_coleta[i]] + valor_erva[i]);
            } else {
                matriz_dp[i][j] = matriz_dp[i - 1][j];
            }
        }
    }

    cout << matriz_dp[qtd_ervas][tempo_total] << endl;
    return 0;
}

Otimização de Espaço (Array Unidimensional)

Podemos reduzir a complexidade de espaço para $O(V)$ utilizando um array de uma única dimensão. Para garantir que cada item seja contado apenas uma vez, o loop interno da capacidade deve ser percorrido de forma reversa (do fim para o início).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int limite_v, n_itens;
    if (!(cin >> limite_v >> n_itens)) return 0;

    vector<int> custos(n_itens + 1);
    vector<int> utilidades(n_itens + 1);
    vector<int> dp_otimizado(limite_v + 1, 0);

    for (int i = 1; i <= n_itens; i++) {
        cin >> custos[i] >> utilidades[i];
    }

    for (int i = 1; i <= n_itens; i++) {
        // Percorrendo de trás para frente para evitar múltiplas contagens do mesmo item
        for (int j = limite_v; j >= custos[i]; j--) {
            dp_otimizado[j] = max(dp_otimizado[j], dp_otimizado[j - custos[i]] + utilidades[i]);
        }
    }

    cout << dp_otimizado[limite_v] << endl;
    return 0;
}

2. Mochila Completa (Unbounded Knapsack)

Diferente da mochila 0/1, na mochila completa temos suprimento ilimitado de cada item. Se um item é vantajoso, podemos pegá-lo várias vezes até esgotar a capacidade.

A lógica de implementação é quase idêntica à versão otimizada da mochila 0/1, mas o loop interno da capacidade deve ser percorrido de forma progressiva (do início para o fim). Isso permite que o cálculo de uma capacidade maior utilize o resultado já atualizado do mesmo item em uma capacidade menor.

for (int i = 1; i <= n_itens; i++) {
    // Ordem direta: permite reutilizar o mesmo item i múltiplas vezes
    for (int j = custos[i]; j <= limite_v; j++) {
        dp_otimizado[j] = max(dp_otimizado[j], dp_otimizado[j - custos[i]] + utilidades[i]);
    }
}

3. Mochila Múltipla (Bounded Knapsack)

Neste caso, cada item $i$ tem uma quantidade limitada $s[i]$. Este problema situa-se entre a Mochila 0/1 e a Mochila Completa.

Existem duas formas principais de resolver:

1. Decomposição Simples: Tratar cada uma das $s[i]$ instâncias como itens individuais e aplicar o algoritmo de Mochila 0/1. No entanto, isso é ineficiente se $s[i]$ for muito grande.
2. Otimização Binária: Decompor a quantidade $s[i]$ em potências de 2 (1, 2, 4, ..., restante). Qualquer número até $s[i]$ pode ser formado pela soma dessas potências. Isso transforma o problema em uma Mochila 0/1 com $O(\log s[i])$ itens por tipo, reduzindo drasticamente o tempo de processamento.