Problema da mochila

2073 palavras 9 páginas
1 INTRODUÇÃO

Uma pergunta muito frequente nas salas de aula hoje em dia é: “Aonde vou aplicar isso na minha vida?”.
O objetivo deste trabalho é de explicar um algoritmo lógico e mostrar a suas aplicações, além demonstrar toda a sua genialidade.

2 PROBLEMA DA MOCHILA

O problema da mochila (em 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 preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.
O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é à base do primeiro algoritmo de chave pública (chaves assimétricas).
Normalmente este problema é resolvido com programação dinâmica, obtendo então a resolução exata do problema, mas também sendo possível usar PSE (procedimento de separação e evolução). Existem também outras técnicas, como usar algoritmo guloso, meta-heurística (algoritmos genéticos) para soluções aproximadas.

3 DEFINIÇÃO

Suponha que tenha uma mochila com capacidade total de e itens distintos. Seja a quantidade de itens que está sendo carregado, cada um com um respectivo peso e valor . Maximizar o valor da mochila nada mais é que maximizar a seguinte equação:

3.1 Problema da Mochila com Repetições

Relacionados

  • Problema da mochila em java
    4821 palavras | 20 páginas
  • Técnica de backtracking
    2856 palavras | 12 páginas
  • nada
    1514 palavras | 7 páginas
  • Crônica: Xixi na calça
    871 palavras | 4 páginas
  • Estágio básico i : observação do comportamento
    4346 palavras | 18 páginas
  • Resumo do filme a meta
    1374 palavras | 6 páginas
  • Técnicas para percorrer trilhas em diferentes terrenos
    1121 palavras | 5 páginas
  • Projeto de Seminario Integrado
    1670 palavras | 7 páginas