1. Problema da Mochila 0/1

A abordagem clássica utiliza uma matriz bidimensional para armazenar os estados, onde dp[i][j] representa o valor máximo obtido considerando os primeiros i itens com uma capacidade restrita a j. A relação de recorrência é definida pela escolha entre incluir ou excluir o item atual.

Para otimizar o uso de memória, é possível reduzir a estrutura para um array unidimensional. A lógica central reside no fato de que, ao calcular o estado para o item i, dependemos apenas dos valores calculados para o item i-1. Portanto, não é necessário manter todo o histórico de itens anteriores.

Ao utilizar um vetor unidimensional dp[j], é crucial iterar sobre a capacidade de trás para frente. Se a iteração fosse feita da esquerda para a direita, poderíamos acabar utilizando o valor atualizado do mesmo item múltiplas vezes na mesma etapa, o que violaria a restrição de escolher cada item apenas uma vez. A atualização reversa garante que usamos sempre os dados da iteração anterior.

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

using namespace std;

constexpr int LIMITE = 1010;
int quantidadeItens, capacidadeMochila;
int pesos[LIMITE], valores[LIMITE];
int dp[LIMITE];

int main() {
    cin >> quantidadeItens >> capacidadeMochila;

    for (int i = 1; i <= quantidadeItens; ++i) {
        cin >> pesos[i] >> valores[i];
    }

    // Processamento com array unidimensional
    for (int i = 1; i <= quantidadeItens; ++i) {
        // Iteração reversa para evitar reutilização do mesmo item
        for (int j = capacidadeMochila; j >= pesos[i]; --j) {
            dp[j] = max(dp[j], dp[j - pesos[i]] + valores[i]);
        }
    }

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

2. Problema da Mochila Completa

Nesta variante, cada item pode ser selecionado infinitamente. A diferença fundamental na implementação otimizada está na ordem da iteração sobre a capacidade. Como podemos reutilizar o item atual, devemos iterar da menor capacidade para a maior. Isso permite que o valor atualizado de dp[j - peso] (que já pode incluir o item atual) seja usado para calcular dp[j].

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1010;
int n, m;
int custo[MAX_N], beneficio[MAX_N];
int tabelaDP[MAX_N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> custo[i] >> beneficio[i];
    }

    for (int i = 1; i <= n; ++i) {
        // Iteração direta permite uso múltiplo do item
        for (int j = custo[i]; j <= m; ++j) {
            tabelaDP[j] = max(tabelaDP[j], tabelaDP[j - custo[i]] + beneficio[i]);
        }
    }

    cout << tabelaDP[m] << endl;
    return 0;
}

3. Problema da Mochila Múltipla

Aqui, cada item possui uma quantidade limitada s. A solução ingênua envolve três loops, o que pode ser computacionalmente custoso. Uma otimização comum utiliza decomposição binária. Qualquer número inteiro pode ser representado pela soma de potências de 2. Assim, dividimos a quantiddae s de cada item em grupos que representam potências de 2 (1, 2, 4, ..., resto). Isso transforma o problema de mochila múltipla em um problema de mochila 0/1 com mais itens, mas com complexidade logarítmica em relação à quantidade.

Otimização Binária

#include <iostream>
#include <vector>

using namespace std;

const int MAX_V = 2010;
const int MAX_ITENS = 12010;

int n, m;
int pesosNovos[MAX_ITENS], valoresNovos[MAX_ITENS];
int dp[MAX_V];

int main() {
    cin >> n >> m;
    int indiceAtual = 0;

    for (int i = 0; i < n; ++i) {
        int p, v, q;
        cin >> p >> v >> q;
        
        int k = 1;
        // Decomposição binária da quantidade
        while (k <= q) {
            indiceAtual++;
            pesosNovos[indiceAtual] = p * k;
            valoresNovos[indiceAtual] = v * k;
            q -= k;
            k *= 2;
        }
        // Adiciona o restante
        if (q > 0) {
            indiceAtual++;
            pesosNovos[indiceAtual] = p * q;
            valoresNovos[indiceAtual] = v * q;
        }
    }

    n = indiceAtual;
    // Aplica lógica de Mochila 0/1
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= pesosNovos[i]; --j) {
            dp[j] = max(dp[j], dp[j - pesosNovos[i]] + valoresNovos[i]);
        }
    }

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

4. Problema da Mochila em Grupos

Neste cenário, os itens são dviididos em grupos. De cada grupo, pode-se escolher no máximo um item. A estrutura de loops requer iterar sobre os grupos, depois sobre a capacidade (de trás para frente, similar ao 0/1) e, internamente, sobre as opções disponíveis dentro do grupo atual.

#include <iostream>
#include <algorithm>

using namespace std;

const int LIMITE_GRUPO = 110;

int numGrupos, capacidadeTotal;
int volumes[LIMITE_GRUPO][LIMITE_GRUPO];
int lucros[LIMITE_GRUPO][LIMITE_GRUPO];
int tamanhoGrupo[LIMITE_GRUPO];
int dp[LIMITE_GRUPO];

int main() {
    cin >> numGrupos >> capacidadeTotal;

    for (int i = 1; i <= numGrupos; ++i) {
        cin >> tamanhoGrupo[i];
        for (int j = 0; j < tamanhoGrupo[i]; ++j) {
            cin >> volumes[i][j] >> lucros[i][j];
        }
    }

    for (int i = 1; i <= numGrupos; ++i) {
        for (int j = capacidadeTotal; j >= 0; --j) {
            for (int k = 0; k < tamanhoGrupo[i]; ++k) {
                if (volumes[i][k] <= j) {
                    dp[j] = max(dp[j], dp[j - volumes[i][k]] + lucros[i][k]);
                }
            }
        }
    }

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