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?
- 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.
- 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.
- 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.
Top comments (0)