Problema da mochila: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 121:
para w = 1 até W:
se <math>w_{j} > w</math>
se<math> K(w,j-1)</math>< <math>K(w –
<math>KEEP(w,j)= 1</math>
Inicializar int remaning_weight = W
▲<code> para item maior que zero:</code>
▲<code> se keep(remaning_weight,item) = 1:</code>
▲= remaning_weight – w(item)</code>
▲item a lista solução</code>
▲<code> item = item – 1</code>
▲<code>Retorne Solução</code>
=== Solução usando Backtracking ===
Backtracking é um algoritmo refinado da busca por força bruta (ou enumeração exaustiva), no qual boa parte das soluções podem ser eliminadas sem serem explicitamente examinadas. É uma estratégia que se aplica em problemas cuja solução pode ser definida a partir de uma seqüência de n decisões, que podem ser modeladas por uma árvore que representa todas as possíveis seqüências de decisão. De fato, se existir mais de uma disponível para cada uma das n decisões, a busca exaustiva da árvore é exponencial. A eficiência desta estratégia depende da possibilidade de limitar a busca, ou seja, podar a árvore, eliminando os ramos que não levam a solução desejada.
| |||