The Unbounded Knapsack Problem

T. C. Hu (), Leo Landa () and Man-Tak Shing ()
Additional contact information
T. C. Hu: University of California, San Diego, Department of Computer Science and Engineering
Leo Landa: University of California, San Diego, Department of Computer Science and Engineering
Man-Tak Shing: Naval Postgraduate School, Department of Computer Science

Chapter 10 in Research Trends in Combinatorial Optimization, 2009, pp 201-217 from Springer

Abstract: Summary This paper presents a survey of the unbounded knapsack problem. We focus on the techniques for obtaining the optimal solutions, particularly those using the periodic structure of the optimal solutions when the knapsack weight-carrying capacity b is sufficiently large. In addition to reviewing existing algorithms on the subject, the paper also includes two new algorithms, one for finding the onset of the optimal periodic solutions in time O(nw 1), where w 1 is the weight of the best item, i.e. the item with the highest value-to-weight ratio, and a second one for finding the optimal solutions when the capacity b is below the critical value where the optimal periodic solution begins. The second algorithm has a worst-case time complexity of O(nw 1 v 1), where v 1 is the value of the best item.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_10

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().