| Article ID: | iaor20022515 |
| Country: | Brazil |
| Volume: | 20 |
| Issue: | 1 |
| Start Page Number: | 117 |
| End Page Number: | 134 |
| Publication Date: | Jun 2000 |
| Journal: | Pesquisa Operacional |
| Authors: | Yanasse H.H., Maculan N., Soma N.Y. |
| Keywords: | computational analysis |
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.