| Revue: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000312999 |
| ISSN: | 0101-7438 |
| Autores: | Yanasse, Horacio Hideki1 Soma, Nei Yoshihiro2 Maculan, Nelson3 |
| Instituciones: | 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 |
| Año: | 2000 |
| Periodo: | Jun |
| Volumen: | 20 |
| Número: | 1 |
| Paginación: | 117-134 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Experimental, aplicado |
| Resumen en inglés | 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 |
| Resumen en portugués | 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 |
| Disciplinas: | Ciencias de la computación, Matemáticas |
| Palabras clave: | 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 |
| Texte intégral: | Texto completo (Ver HTML) |
