An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem
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.
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Pesquisa Operacional
2000
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382000000100011 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|