Problema da mochila: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel |
|||
Linha 3:
[[Imagem:Knapsack.svg|thumb|Problema da mochila: Como maximizar o valor com um peso máximo?]]
[[File:Mochilaproblema.png|thumb|Problema da Mochila acima resolvido no Processing.]]
O '''problema da mochila''' (em [[Língua inglesa|inglês]], ''Knapsack problem'') é um problema de [[optimização combinatória]]. O nome dá-se devido ao modelo de uma situação em que é necessário
O problema da mochila é um dos 21 problemas [[NP-completo]]s de [[Richard Karp]], exposto em [[1972]]. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é a base do primeiro [[algoritmo]] de chave pública (chaves assimétricas).<ref>Edwin D. Reilly, ''Concise Encyclopedia of Computer Science'', p.562</ref>
| |||