Problema da mochila: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
A wikipédia não é um repositório de implementações de um algoritmo em várias linguagens. Para isso existe http://rosettacode.org/wiki/Knapsack_problem |
Pseudocódigo para a matriz keep que serve para retornar os itens da solução ótima Etiquetas: Espaçamento excessivo Editor Visual |
||
Linha 115:
retornar <math>K(W,n)</math>
=== Matriz keep para o caso Limitado 0/1 ===
<code>Inicializar KEEP(0,j) = 0 para todo j pertencente a {1,...,n} e KEEP(w,0) = 0 para todo w pertencente a {1,...,n}:</code>
<code>para j = 1 até n: </code>
<code>para w = 1 até W:</code>
<code>se wj <= w:</code>
<code> se K(w,j-1)<K(w – wj, j – 1) + vj :</code>
<code> KEEP(w,j)
= 1</code>
<code>Inicializar inteiro item = n</code>
<code>Inicializar int remaning_weight = W</code>
<code>Inicializar lista solução = vazio</code>
<code> para item maior que zero:</code>
<code> se keep(remaning_weight,item) = 1:</code>
<code> remaning_weight
= remaning_weight – w(item)</code>
<code> adicione
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.
| |||