Introdução

Este artigo apresenta quatro tipos clássicos de problemas de mochila, organizados no seguinte mapa conceitual:

I. Mochila 01

Temos N itens e uma mochila com capacidade máxima M. O item i possui peso wi e valor vi. Dado o limite de peso da mochila, quais itens devem ser selecionados para maximizar o valor total?

Como cada item pode ser escolhido ou não exatamente uma vez, este problema é conhecido como Mochila 01.

Link do problema: AcWing 2. Problema da Mochila 01

#include <bits/stdc++.h>

using namespace std;

const int MAX_ITEMS = 1010;

int itemWeight[MAX_ITEMS], itemValue[MAX_ITEMS];
int dynamicTable[MAX_ITEMS][MAX_ITEMS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;
    
    for (int i = 1; i <= quantity; i++) {
        cin >> itemWeight[i] >> itemValue[i];
    }

    for (int i = 1; i <= quantity; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < itemWeight[i]) {
                dynamicTable[i][j] = dynamicTable[i - 1][j];
            } else {
                dynamicTable[i][j] = max(
                    dynamicTable[i - 1][j],
                    dynamicTable[i - 1][j - itemWeight[i]] + itemValue[i]
                );
            }
        }
    }

    cout << dynamicTable[quantity][capacity] << "\n";

    return 0;
}

A complexidade temporal deste algoritmo é O(n × m).

1.1 Otimização com Array Unidimensional

Essa expressão é fundamental e será utilizada novamente quando abordarmos a mochila completa.

Na verdade, é incorreto afirmar isso. Se iterarmos j em ordem decrescente, o problema não ocorre.

#include <bits/stdc++.h>

using namespace std;

const int MAX_CAPACITY = 1010;

int itemWeight[MAX_CAPACITY], itemValue[MAX_CAPACITY];
int dp[MAX_CAPACITY];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;
    
    for (int i = 1; i <= quantity; i++) {
        cin >> itemWeight[i] >> itemValue[i];
    }

    for (int i = 1; i <= quantity; i++) {
        for (int j = capacity; j >= itemWeight[i]; j--) {
            dp[j] = max(dp[j], dp[j - itemWeight[i]] + itemValue[i]);
        }
    }

    cout << dp[capacity] << "\n";

    return 0;
}

Além disso, os arrays itemWeight e itemValue podem ser eliminados, processando os dados durante a entrada. Isso resulta na versão otimizada final:

#include <bits/stdc++.h>

using namespace std;

const int MAX_CAPACITY = 1010;

int dp[MAX_CAPACITY];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;

    for (int i = 1; i <= quantity; i++) {
        int peso, valor;
        cin >> peso >> valor;
        for (int j = capacity; j >= peso; j--) {
            dp[j] = max(dp[j], dp[j - peso] + valor);
        }
    }

    cout << dp[capacity];

    return 0;
}

Em resumo, quando a tabela dp é bidimensional, j pode ser percorrido em qualquer direção. Entretanto, quando usamos um array unidimensional, j deve ser percorrido de forma decrescente.

II. Mochila Compleat

Temos N tipos de itens e uma mochila com capacidade máxima M. Cada tipo de item possui quantidade ilimitada. O tipo i tem peso wi e valor vi. Dado o limite de peso da mochila, quais combinações de itens maximizam o valor total?

Link do problema: AcWing 3. Problema da Mochila Completa

#include <bits/stdc++.h>

using namespace std;

const int MAX_ITEMS = 1010;

int itemWeight[MAX_ITEMS], itemValue[MAX_ITEMS];
int dynamicTable[MAX_ITEMS][MAX_ITEMS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;
    
    for (int i = 1; i <= quantity; i++) {
        cin >> itemWeight[i] >> itemValue[i];
    }

    for (int i = 1; i <= quantity; i++) {
        for (int j = 1; j <= capacity; j++) {
            int maxQuantity = j / itemWeight[i];
            for (int k = 0; k <= maxQuantity; k++) {
                dynamicTable[i][j] = max(
                    dynamicTable[i][j],
                    dynamicTable[i - 1][j - k * itemWeight[i]] + k * itemValue[i]
                );
            }
        }
    }

    cout << dynamicTable[quantity][capacity] << "\n";

    return 0;
}

2.1 Otimização com Array Unidimensional

Com base na seção 1.1, esta iteração corresponde a percorrer j em ordem crescente. Portanto, basta modifciar a direção da iteração de j no código da Mochila 01.

#include <bits/stdc++.h>

using namespace std;

const int MAX_CAPACITY = 1010;

int dp[MAX_CAPACITY];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;

    for (int i = 1; i <= quantity; i++) {
        int peso, valor;
        cin >> peso >> valor;
        for (int j = peso; j <= capacity; j++) {
            dp[j] = max(dp[j], dp[j - peso] + valor);
        }
    }

    cout << dp[capacity] << "\n";

    return 0;
}

A complexidade temporal após otimização permanece O(n × m).

III. Mochila Múltipla

Temos N tipos de itens e uma mochila com capacidade máxima M. O tipo i possui si unidades disponíveis, peso wi e valer vi. Dado o limite de peso da mochila, quais combinações maximizam o valor total?

Link do problema: AcWing 4. Problema da Mochila Múltipla

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110;

int dp[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;

    for (int i = 1; i <= quantity; i++) {
        int peso, valor, quantidade;
        cin >> peso >> valor >> quantidade;
        for (int j = 1; j <= capacity; j++) {
            int maxPossible = min(quantidade, j / peso);
            for (int k = 0; k <= maxPossible; k++) {
                dp[i][j] = max(
                    dp[i][j],
                    dp[i - 1][j - k * peso] + k * valor
                );
            }
        }
    }

    cout << dp[quantity][capacity] << "\n";

    return 0;
}

3.1 Otimização Binária

Link do problema: AcWing 5. Problema da Mochila Múltipla II

#include <bits/stdc++.h>

using namespace std;

const int MAX_ITEMS = 11010;
const int MAX_CAPACITY = 2010;

int weight[MAX_ITEMS], value[MAX_ITEMS];
int dp[MAX_CAPACITY];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;

    int totalItems = 0;
    while (quantity--) {
        int peso, valor, qtde;
        cin >> peso >> valor >> qtde;
        for (int power = 1; power <= qtde; power *= 2) {
            totalItems++;
            weight[totalItems] = peso * power;
            value[totalItems] = valor * power;
            qtde -= power;
        }
        if (qtde > 0) {
            totalItems++;
            weight[totalItems] = peso * qtde;
            value[totalItems] = valor * qtde;
        }
    }

    quantity = totalItems;
    for (int i = 1; i <= quantity; i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << dp[capacity] << "\n";

    return 0;
}

IV. Mochila Agrupada

Temos N grupos de itens e uma mochila com capacidade máxima M. Cada grupo contém vários itens, porém no máximo um item de cada grupo pode ser selecionado. Cada item possui peso wij e valor vij, onde i representa o grupo e j representa o índice dentro do grupo. Dado o limite de peso da mochila, quais combinações maximizam o valor total?

Link do problema: AcWing 9. Problema da Mochila Agrupada

#include <bits/stdc++.h>

using namespace std;

const int MAX_GROUPS = 110;

int weight[MAX_GROUPS][MAX_GROUPS];
int value[MAX_GROUPS][MAX_GROUPS];
int groupSize[MAX_GROUPS];
int dp[MAX_GROUPS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int quantity, capacity;
    cin >> quantity >> capacity;
    
    for (int i = 1; i <= quantity; i++) {
        cin >> groupSize[i];
        for (int j = 1; j <= groupSize[i]; j++) {
            cin >> weight[i][j] >> value[i][j];
        }
    }

    for (int i = 1; i <= quantity; i++) {
        for (int j = capacity; j >= 1; j--) {
            for (int k = 1; k <= groupSize[i]; k++) {
                if (j >= weight[i][k]) {
                    dp[j] = max(dp[j], dp[j - weight[i][k]] + value[i][k]);
                }
            }
        }
    }

    cout << dp[capacity] << "\n";

    return 0;
}

Conclusão

Podemos representar a Mochila 01, Completa e Múltipla através de uma fórmula unificada: