Problema da Mochila

O Problema da Mochila

O problema da mochila é um desafio clássico de otimização: dado um conjunto de itens com valores e pesos específicos, determine quais itens incluir de forma que o peso total seja menor ou igual a um limite determinado (a capacidade da mochila) e que o valor total seja o maior possível.

Esta ferramenta interativa permite que você explore o problema utilizando diferentes algoritmos de resolução, cada um com suas próprias características de eficiência e garantias de solução. Você pode comparar os resultados e o número de etapas necessárias para cada abordagem.

Sobre os Algoritmos

Cada algoritmo implementado tem características únicas:

Força Bruta: Garante a solução ótima mas é ineficiente para muitos itens (2^n combinações).
Programação Dinâmica: Eficiente para problemas com capacidade moderada (O(n*W)).
Algoritmo Guloso: Rápido mas não garante solução ótima, usa razão valor/peso.
Branch and Bound: Mais eficiente que força bruta, usa poda de ramos.
Algoritmo Genético: Boa para problemas grandes, usa evolução de população.
Simulated Annealing: Boa para problemas grandes, pode escapar de ótimos locais.
Aproximação: Rápido, garante pelo menos 50% do valor ótimo.
FPTAS: Pode chegar arbitrariamente perto da solução ótima.

Solucionador Interativo do Problema da Mochila

O Problema da Mochila

Painel de Controle

Itens

Sua Mochila

Seleção Atual

Solução Ótima

Melhor Valor

Peso Total

Etapas

Tempo de Execução

Sobre os Algoritmos

O Problema da Mochila

Painel de Controle

Itens

Sua Mochila

Seleção Atual

Solução Ótima

Melhor Valor

Peso Total

Etapas

Tempo de Execução

Sobre os Algoritmos

Etapas do Algoritmo

Detalhes da Execução

Explicação do Algoritmo