O problema da Mochila 0/1 (maximizar o valor de itens em uma mochila com peso limitado) não pode ser resolvido por um Algoritmo Guloso simples. Isso ocorre porque o problema não satisfaz a propriedade da escolha gulosa, exigindo uma solução por Programação Dinâmica. Qual é a falha principal do método guloso neste contexto?
Questão
O problema da Mochila 0/1 (maximizar o valor de itens em uma mochila com peso limitado) não pode ser resolvido por um Algoritmo Guloso simples. Isso ocorre porque o problema não satisfaz a propriedade da escolha gulosa, exigindo uma solução por Programação Dinâmica. Qual é a falha principal do método guloso neste contexto?
Alternativas
Não é possível definir o caso base para o problema.
A solução ótima não pode ser construída a partir de subsoluções.
O algoritmo guloso só funciona para problemas de tempo constante O(1).
A escolha localmente mais vantajosa (ex: maior valor por peso) pode impedir uma solução globalmente mais lucrativa.
Explicação
No problema da Mochila 0/1, os itens são indivisíveis (ou pega ou não pega). Por isso, uma regra gulosa “natural” (como escolher sempre o item com maior valor/peso) pode “consumir” parte da capacidade e bloquear combinações de itens que, juntas, dariam um valor total maior.
Em outras palavras, o problema não tem a propriedade da escolha gulosa: a melhor escolha local (melhor densidade valor/peso naquele momento) não garante que exista uma solução ótima global que contenha essa escolha. Há contraexemplos clássicos em que o item com melhor razão valor/peso leva a uma solução pior do que outra combinação de itens com razões individuais menores. (cl.cam.ac.uk)
Isso é justamente a falha principal do método guloso aqui: ele toma decisões irreversíveis “míopes” e pode impedir o ótimo global, enquanto a Programação Dinâmica compara sistematicamente as possibilidades (pegar ou não pegar cada item) para encontrar o melhor conjunto. (users.ece.utexas.edu)