PROBLEMA DA MOCHILA
449 palavras
2 páginas
PROBLEMA DA MOCHILAGrabriela Angela Severgnini
Rosana Alicrim
O que é o problema da mochila?
É um problema de otimização combinatória;
Dados n objetos com valor e peso e uma mochila que suporta peso máximo W.
Determinar um subconjunto de objetos de valor máximo e cujo peso não excede W.
Objetos: x1, x2,…,xn.
Valores: v1, v2, …, vn.
Pesos: p1, p2,…, pn.
História
• Também conhecido como “Knapsack
Problem”;
• O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em seu artigo, em 1972;
• É a base para o primeiro Algoritmo, em 1976;
Tipos de Mochilas
Métodos de Resolução
• Programação Dinâmica;
• Método Guloso;
• Backtracking;
• Por aproximação;
• Meta-heuristicas;
Programação Dinâmica
• Foi a primeira técnica mais inteligente utilizada para resolver o problema, na década de 50;
• É um método aprimorado que ao invés de chamar uma função várias vezes ele, na primeira vez que é chamado, armazena o resultado para que cada vez que a função for chamada novamente volte o resultado;
• Define-se uma função como solução ótima: f(i, w)
• O objeto xn pode ou não estar na solução ótima; • Se pn > W: não está na solução ótima; f(i-1, w)
• Se pn ≤ W: está na solução ótima; f(i-1, w-pn) + Vn f(i-1, w)
Exemplo:
Capacidade da mochila (W): 7 kg
Objetos: x1, x2, x3 e x4;
Valores: 10, 7, 25 e 24;
Pesos: 2, 1, 6 e 5;
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
0
10
10
10
10
10
10
2
0
7
10
17
17
17
17
17
3
0
7
10
17
17
17
25
32
4
0
7
10
17
17
24
31
34
i
w
Método Guloso
• É um dos algoritmos mais simples;
• O algoritmo trabalha em estágios, considerando uma entrada por vez;
• Em cada estágio é tomada uma decisão considerando se uma entrada particular é uma solução ótima;
Backtracking
• Também conhecido como Força Bruta;
• Apresenta a resolução mais óbvia;
• Compara todas as possibilidades até encontrar a melhor;
Vantagem :
Este algoritmo devolve a resposta correta.
Desvantagem :
Quando