Mochila 0/1 (0/1 Knapsack)

O problema da Mochila 0/1 restringe a seleção de cada item a, no máximo, uma única vez. Embora possa ser resolvido utilizando uma matriz bidimensional para rastrear os estados, é possível otimizar o consumo de memória reduzindo a estrutura para um array unidimensional.

A chave para a otimização unidimensional reside na ordem de iteração da capacidade da mochila. Ao percorrer a capacidade de forma decrescente (do valor máximo até o peso do item atual), garantimos que o estado atual seja calculado com base nos resultados da iteração anterior do item, impedindo que o mesmo item seja incluído mais de uma vez.

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

using namespace std;

int main() {
    int max_capacity, item_count;
    if (!(cin >> max_capacity >> item_count)) return 0;

    vector<int> weights(item_count), values(item_count);
    for (int i = 0; i < item_count; ++i) {
        cin >> weights[i] >> values[i];
    }

    // Inicializado com -1 para indicar estados inalcançáveis, exceto a capacidade 0
    vector<int> dp(max_capacity + 1, -1);
    dp[0] = 0;

    for (int i = 0; i < item_count; ++i) {
        // Iteração decrescente para garantir a propriedade 0/1
        for (int c = max_capacity; c >= weights[i]; --c) {
            if (dp[c - weights[i]] != -1) {
                dp[c] = max(dp[c], dp[c - weights[i]] + values[i]);
            }
        }
    }

    int best_value = -1;
    for (int c = 0; c <= max_capacity; ++c) {
        best_value = max(best_value, dp[c]);
    }

    cout << best_value << "\n";
    return 0;
}

Mochila Ilimitada (Unbounded Knapsack)

Na variação ilimitada, cada tipo de item pode ser selecionado um número infinito de vezes. A estrutura de programação dinâmica é quase idêntica à da Mochila 0/1, com uma diferença fundamental na direção do loop da capacidade.

Para permitir a reutilização do mesmo item, a capacidade deve ser iterada de forma crescente (do peso do item até a capacidade máxima). Dessa forma, ao calcular o estado atual, o algoritmo pode utilizar um estado que já incluiu o item corrente na mesma iteração.

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

using namespace std;

int main() {
    int max_capacity, item_count;
    if (!(cin >> max_capacity >> item_count)) return 0;

    vector<int> weights(item_count), values(item_count);
    for (int i = 0; i < item_count; ++i) {
        cin >> weights[i] >> values[i];
    }

    vector<int> dp(max_capacity + 1, 0);

    for (int i = 0; i < item_count; ++i) {
        // Iteração crescente para permitir múltiplas escolhas do mesmo item
        for (int c = weights[i]; c <= max_capacity; ++c) {
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i]);
        }
    }

    cout << dp[max_capacity] << "\n";
    return 0;
}

Mochila Limitada (Bounded Knapsack)

Neste modelo, cada item possui uma quantidade máxima disponível. A abordagem mais ingênua consiste em tratar cada unidade do item como um item individual, o que resulta em uma complexidade de tempo excessiva. Para otimizar esse processo, utiliza-se a Decomposição Binária.

A decomposição binária baseia-se no princípio de que qualquer número inteiro pode ser representado como a soma de potências de 2 (ex: $2^0, 2^1, 2^2, \dots$). Em vez de processar $C_i$ unidades individualmante, agrupamos as unidades em pacotes de tamanhos $1, 2, 4, \dots, 2^k$ e o restante. Isso reduz a complexidade de $O(C_i)$ para $O(\log C_i)$ por tipo de item, mantendo a capacidade de formar qualquer quantidade até o limite original.

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

using namespace std;

int main() {
    int max_capacity, item_count;
    if (!(cin >> max_capacity >> item_count)) return 0;

    vector<int> weights(item_count), values(item_count), counts(item_count);
    for (int i = 0; i < item_count; ++i) {
        cin >> weights[i] >> values[i] >> counts[i];
    }

    vector<int> dp(max_capacity + 1, 0);

    for (int i = 0; i < item_count; ++i) {
        int remaining = counts[i];
        int k = 1;
        
        // Decomposição binária das quantidades
        while (remaining > 0) {
            int current_count = min(k, remaining);
            int w = weights[i] * current_count;
            int v = values[i] * current_count;
            
            // Aplica a lógica da mochila 0/1 para os pacotes criados
            for (int c = max_capacity; c >= w; --c) {
                dp[c] = max(dp[c], dp[c - w] + v);
            }
            
            remaining -= current_count;
            k *= 2;
        }
    }

    cout << dp[max_capacity] << "\n";
    return 0;
}

Mochila Agrupada (Grouped Knapsack)

No problema da Mochila Agrupada, os itens são divididos em grupos distintos. A restrição principal é que, no máximo, um único item pode ser selecionado de cada grupo. A ordem dos loops de iteração é o aspecto mais crítico desta variação.

A estrutura correta exige que o loop mais externo itere sobre os grupos, o loop intermediário itere sobre a capacidade da mochila (em ordem decrescente) e o loop mais interno itere sobre os itens dentro do grupo atual. Se a capacidade e os itens do grupo forem invertidos, o algoritmo acabaria permitindo a seleção de múltiplos itens do mesmo grupo, violando a restrição do problema. Na perspectiva da programação dinâmica, o grupo representa o "estágio", a capacidade e o grupo formam o "estado", e a escolha do item é a "decisão".

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

using namespace std;

int main() {
    int max_capacity, group_count;
    if (!(cin >> group_count >> max_capacity)) return 0;

    vector<vector<int>> weights(group_count), values(group_count);
    for (int i = 0; i < group_count; ++i) {
        int items_in_group;
        cin >> items_in_group;
        weights[i].resize(items_in_group);
        values[i].resize(items_in_group);
        for (int j = 0; j < items_in_group; ++j) {
            cin >> weights[i][j] >> values[i][j];
        }
    }

    vector<int> dp(max_capacity + 1, 0);

    for (int i = 0; i < group_count; ++i) {
        // Capacidade em ordem decrescente
        for (int c = max_capacity; c >= 0; --c) {
            // Iteração sobre os itens do grupo atual
            for (int j = 0; j < weights[i].size(); ++j) {
                if (c >= weights[i][j]) {
                    dp[c] = max(dp[c], dp[c - weights[i][j]] + values[i][j]);
                }
            }
        }
    }

    cout << dp[max_capacity] << "\n";
    return 0;
}

Mochila em Árvore (Tree Knapsack)

A Mochila em Árvore é uma extensão avançada onde a seleção de itens possui dependências hierárquicas estruturadas em forma de árvore. Um exemplo clássico é o problema de seleção de cursos, onde um curso pré-requisito deve ser selecionado antes de seus cursos dependentes. A resolução deste modelo geralmente combina a travessia em árvore (como pós-ordem) com a tabela de programação dinâmica da mochila, fundindo a estrutura de dados da árvore com as transições de estado da capacidade.