Desafio da Mochila (Knapsack Problem) em PHP

Resolvi trazer neste artigo um problema relativamente simples, que aprendi a bastante tempo atrás, um dos problemas de otimização mais famosos da computação: o desafio da mochila.

É bem simples, mas há pouco tempo, desenvolvendo um sistema de LMS para meu trabalho, me deparei com um problema exatamente igual, porém envolvendo notas e questionários. Por isso, hoje vou resolver esse problema de forma bem simples e prática utilizando nosso guerreiro PHP.

O desafio é o seguinte, imagine que você está se preparando para uma aventura e tem que escolher o que levar na mochila. Só tem um problema... a mochila tem um limite de peso, e você precisa escolher o que levar para maximizar o valor total.

Você pode ser informar melhor sobre esse problema neste link: https://pt.wikipedia.org/wiki/Problema_da_mochila

O que temos aqui é um problema de escolha. Dado um número de itens, cada um com um valor e um peso, precisamos decidir quais itens colocar na mochila para maximizar o valor, sem exceder a capacidade de peso da mochila.

Dados e regras do desafio:

• A capacidade da mochila (quantidade máxima de peso que podemos carregar).
• Uma lista de itens, onde cada item tem um peso e um valor.

Cada item pode ser levado ou deixado, ou seja, é uma decisão binária. E não dá pra dividir o item, ou leva o item inteiro ou nada.

O objetivo é simples: encontrar o valor máximo que conseguimos carregar sem ultrapassar a capacidade.

A solução: programação dinâmica

Para resolver o problema da mochila, vamos usar a boa e velha programação dinâmica. A ideia é construir uma tabela que vai armazenando os valores máximos possíveis para cada capacidade da mochila, conforme a gente decide incluir ou não cada item.

Como faremos:

• Criamos uma matriz onde as linhas representam os itens e as colunas representam as capacidades (de 0 até a capacidade máxima).
• Cada célula dessa tabela vai guardar o valor máximo que conseguimos atingir até aquele momento.
• Para cada item, decidimos se vamos colocá-lo na mochila ou não, comparando o valor de incluir versus deixar o item de fora.

function mochila($capacidade, $pesos, $valores, $n) {
    // Criando uma tabela para armazenar os valores máximos possíveis
    $dp = array_fill(0, $n + 1, array_fill(0, $capacidade + 1, 0));

    // Preenchendo a tabela com os valores
    for ($i = 1; $i <= $n; $i++) { // Iterando sobre os itens
        for ($w = 1; $w <= $capacidade; $w++) { // Iterando sobre as capacidades
            if ($pesos[$i - 1] <= $w) {
                // Se o item cabe na mochila, decidimos se vamos colocar ele ou não
                $dp[$i][$w] = max(
                    $valores[$i - 1] + $dp[$i - 1][$w - $pesos[$i - 1]], // Colocamos o item
                    $dp[$i - 1][$w] // Deixamos o item de fora
                );
            } else {
                // Se o item não cabe, apenas seguimos sem ele
                $dp[$i][$w] = $dp[$i - 1][$w];
            }
        }
    }

    // Retorna o valor máximo que pode ser colocado na mochila
    return $dp[$n][$capacidade];
}

// Exemplo de uso:
$valores = [60, 100, 120]; // Valores dos itens (ex: dinheiro)
$pesos = [10, 20, 30]; // Pesos dos itens (ex: kg)
$capacidade = 50; // Capacidade máxima da mochila (ex: quantos kg podemos carregar)
$n = count($valores); // Quantidade de itens

// Chamamos a função e imprimimos o valor máximo possível:
echo "Valor máximo que pode ser levado: " . mochila($capacidade, $pesos, $valores, $n);

O está acontecendo aqui?

1. Função mochila: Ela recebe a capacidade da mochila, os arrays de pesos e valores dos itens e o número total de itens. Cria uma tabela dp onde cada célula guarda o valor máximo possível para aquela capacidade e aquele conjunto de itens.
2. Preenchimento da tabela: Para cada item, verificamos se podemos colocá-lo na mochila, comparando o valor de incluir o item (se couber) com o valor de não incluí-lo. Assim, vamos atualizando a tabela com o valor máximo em cada passo.
3. Resultado final: No fim, a célula dp[n][capacidade] vai ter o valor máximo que conseguimos alcançar com os itens e capacidade.

Conclusão

Bom, é isso ai! Essa foi uma implementação bem simples em PHP, mas é prática e pode ser facilmente adaptada para resolver problemas semelhantes em outros cenários.