2000-06
An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem
Neste trabalho apresenta-se um esquema enumerativo para se determinar as K-melhores (K > 1) soluções para o problema da mochila unidimensional. Se n é o número total de itens diferentes e b é a capacidade da mochila, a complexidade computacional do esquema proposto é limitado por O(Knb). O algoritmo foi implementado em uma estação de trabalho e testes computacionais foram realizados variando-se diferentes parâmetros do problema.
Texto completo-
Assuntos:
- Problema da mochila
- K-melhores soluções