| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000312999 |
| ISSN: | 0101-7438 |
| Authors: | Yanasse, Horacio Hideki1 Soma, Nei Yoshihiro2 Maculan, Nelson3 |
| Institutions: | 1Instituto Nacional de Pesquisas Espaciais, Laboratorio Associado de Computacao e Matematica Aplicada, Sao Jose dos Campos, Sao Paulo. Brasil 2Instituto Tecnologico de Aeronautica, Divisao de Ciencia da Computacao, Sao Jose dos Campos, Sao Paulo. Brasil 3Universidade Federal do Rio de Janeiro, Instituto Alberto Luiz Coimbra de Pos-Graduacao e Pesquisa de Engenharia, Rio de Janeiro. Brasil |
| Year: | 2000 |
| Season: | Jun |
| Volumen: | 20 |
| Number: | 1 |
| Pages: | 117-134 |
| Country: | Brasil |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Experimental, aplicado |
| English abstract | In this work we present an enumerative scheme for determining the K-best solutions (K > 1) of the one dimensional knapsack problem. If n is the total number of different items and b is the knapsack's capacity, the computational complexity of the proposed scheme is bounded by O(Knb) with memory requirements bounded by O(nb). The algorithm was implemented in a workstation and computational tests for varying values of the parameters were performed |
| Portuguese abstract | 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 |
| Disciplines: | Ciencias de la computación, Matemáticas |
| Keyword: | Análisis de sistemas, Matemáticas aplicadas, Problema de la mochila, K-mejores soluciones, Algoritmos |
| Keyword: | Computer science, Mathematics, Systems analysis, Applied mathematics, Knapsack problem, K-best solutions, Algorithms |
| Full text: | Texto completo (Ver HTML) |
