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

No cenário clássico da mochila 0/1, dispomos de $N$ itens e uma mochila com capacidade máxima $V$. Cada item possui um volume $v_i$ e um valor $w_i$. A restrição fundamental é que **cada item pode ser escolhido apenas uma vez**. O objetivo é maximizar o valor total sem exceder a capacidade $V$. ### Definição de Estado

Definimos $f[i][j]$ como o valor máximo obtido considerando os primeiros $i$ itens com uma capacidade disponível de $j$.

Transição de Estado

Para cada item $i$, temos duas opções:

1. Não incluir o item: O valor permanece $f[i-1][j]$.
2. Incluir o item: O valor torna-se $f[i-1][j - v_i] + w_i$ (se $j \ge v_i$).

A equação de recorrência é: $f[i][j] = \max(f[i-1][j], f[i-1][j - v_i] + w_i)$.

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

using namespace std;

int main() {
    int n, cap_max;
    cin >> n >> cap_max;
    
    vector<int> volumes(n + 1), valores(n + 1);
    vector<vector<int>> dp(n + 1, vector<int>(cap_max + 1, 0));

    for(int i = 1; i <= n; i++) cin >> volumes[i] >> valores[i];

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= cap_max; j++) {
            dp[i][j] = dp[i-1][j];
            if(j >= volumes[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - volumes[i]] + valores[i]);
            }
        }
    }
    cout << dp[n][cap_max] << endl;
    return 0;
}

Otimização de Espaço

Como o estado $i$ depende apenas do estado $i-1$, podemos reduzir a matriz para um array unidimensional. Para evitar usar o mesmo item múltiplas vezes na mesma iteração, percorremos a capacidade de forma decrescente.

for(int i = 1; i <= n; i++) {
    for(int j = cap_max; j >= volumes[i]; j--) {
        f[j] = max(f[j], f[j - volumes[i]] + valores[i]);
    }
}

2. Problema da Mochila Completa (Unbounded Knapsack)

Diferente do modelo anterior, aqui **cada item está disponível em quantidades infinitas**. ### Abordagem de Programação Dinâmica

A transição de estado para a mochila completa é simplificada para: $f[i][j] = \max(f[i-1][j], f[i][j - v_i] + w_i)$. Note que o segundo termo utiliza $f[i]$, permitindo múltiplas inclusões do mesmo item.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(m + 1, 0);

    for(int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        // Ordem crescente permite reutilizar o item i
        for(int j = v; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

3. Problema da Mochila Múltipla (Bounded Knapsack)

Nesta variação, cada item $i$ tem um limite de $s_i$ unidades disponíveis. ### Otimização Binária

Aumentar a eficiência decompondo a quantidade $s_i$ em potências de 2. Qualquer número entre $0$ e $s_i$ pode ser representado pela soma de elementos do conjunto $\{1, 2, 4, \dots, 2^k, R\}$. Isso transforma o problema em uma mochila 0/1 com $O(N \log S)$ itens.

#include <iostream>
#include <vector>

using namespace std;

struct Item {
    int vol, val;
};

int main() {
    int n, capacidade;
    cin >> n >> capacidade;
    vector<Item> novos_itens;

    for(int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2) {
            s -= k;
            novos_itens.push_back({v * k, w * k});
        }
        if(s > 0) novos_itens.push_back({v * s, w * s});
    }

    vector<int> dp(capacidade + 1, 0);
    for(auto &item : novos_itens) {
        for(int j = capacidade; j >= item.vol; j--) {
            dp[j] = max(dp[j], dp[j - item.vol] + item.val);
        }
    }
    cout << dp[capacidade] << endl;
    return 0;
}

4. Problema da Mochila em Grupos (Grouped Knapsack)

Neste modelo, os itens são divididos em grupos. De cada grupo, **no máximo um item** pode ser escolhido. ### Lógica de Resolução

Para cada grupo, decidimos qual item levar (ou nenhum). A estrutura de loops deve garantir que apenas um item por grupo seja contabilizado.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n_grupos, m_capacidade;
    cin >> n_grupos >> m_capacidade;
    vector<int> f(m_capacidade + 1, 0);

    for(int i = 0; i < n_grupos; i++) {
        int qtd_no_grupo;
        cin >> qtd_no_grupo;
        vector<pair<int, int>> itens_grupo(qtd_no_grupo);
        for(int k = 0; k < qtd_no_grupo; k++) cin >> itens_grupo[k].first >> itens_grupo[k].second;

        for(int j = m_capacidade; j >= 0; j--) {
            for(int k = 0; k < qtd_no_grupo; k++) {
                int vol = itens_grupo[k].first;
                int val = itens_grupo[k].second;
                if(j >= vol) {
                    f[j] = max(f[j], f[j - vol] + val);
                }
            }
        }
    }
    cout << f[m_capacidade] << endl;
    return 0;
}