Abordagens para Diferentes Tipos de Problema da Mochila

O problema da mochila é um clássico em programação dinâmica. As variações principais — mochila 0-1, completa e múltipla — exigem estratégias distintas de resolução, com abordagens que diferem principalmente na direção do percurso e no tratamento dos itens.

Mochila 0-1

Em cada item, há apenas duas opções: incluí-lo ou não. A solução utiliza uma matriz de programação dinâmica ou um array unidimensional com atualização reversa para evitar uso múltiplo do mesmo item.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_CAPACITY = 1005;
const int MAX_ITEMS = 205;

int weights[MAX_ITEMS];
int values[MAX_ITEMS];
int dp[MAX_CAPACITY];

int main() {
    int capacity, num_items;
    scanf("%d%d", &capacity, &num_items);

    for (int i = 0; i < num_items; ++i) {
        scanf("%d%d", &weights[i], &values[i]);
    }

    for (int i = 0; i < num_items; ++i) {
        for (int j = capacity; j >= weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    printf("%d\n", dp[capacity]);
    return 0;
}

Mochila Completa

Cada item pode ser usado infinitamente. A diferença chave está na direção do laço interno: agora ele percorre em ordem crescente, permitindo múltiplas inclusões do mesmo item.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_CAPACITY = 100000;
const int MAX_ITEMS = 1000;

int weights[MAX_ITEMS];
int values[MAX_ITEMS];
int dp[MAX_CAPACITY];

int main() {
    int capacity, num_items;
    scanf("%d%d", &capacity, &num_items);

    for (int i = 0; i < num_items; ++i) {
        scanf("%d%d", &weights[i], &values[i]);
    }

    for (int i = 0; i < num_items; ++i) {
        for (int j = weights[i]; j <= capacity; ++j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    printf("%d\n", dp[capacity]);
    return 0;
}

Mochila Múltipla com Otimização Binária

Cada item tem uma quantidade máxima disponível. Em vez de tratar cada instância individualmente (o que levaria a complexidade excessiva), usa-se a representação binária para dividir o número total de itens em potências de dois, reduzindo drasticamente o número de novos itans gerados.

Por exemplo, 19 pode ser escrito como \(1 + 2 + 4 + 8 + 3\), ou seja, \(2^0 + 2^1 + 2^2 + 2^3 + 3\). Assim, 19 itens idênticos são convertidos em 5 novos tipos, cada um com peso e valor multiplicado pela potência corrrespondente.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 40005;

int dp[MAX_SIZE];
int new_values[MAX_SIZE * 2];
int new_weights[MAX_SIZE * 2];

int main() {
    int num_types, max_weight;
    scanf("%d%d", &num_types, &max_weight);

    int value, weight, count;
    int idx = 1;

    for (int i = 0; i < num_types; ++i) {
        scanf("%d%d%d", &value, &weight, &count);
        for (int k = 1; k <= count; k <<= 1) {
            new_values[idx] = value * k;
            new_weights[idx] = weight * k;
            count -= k;
            idx++;
        }
        if (count > 0) {
            new_values[idx] = value * count;
            new_weights[idx] = weight * count;
            idx++;
        }
    }

    for (int i = 1; i < idx; ++i) {
        for (int j = max_weight; j >= new_weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - new_weights[i]] + new_values[i]);
        }
    }

    printf("%d\n", dp[max_weight]);
    return 0;
}