A polynomial-time algorithm for knapsack with divisible item sizes

W.F.J. Verhaegh, E.H.L. Aarts

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

We consider the special case of the bounded knapsack problem with divisible item sizes, and present an algorithm that solves it in polynomial time. The main characteristic of the algorithm is the fact that it handles the items in order of increasing size, in contrast to known polynomial algorithms for the unbounded knapsack problem.
Original languageEnglish
Pages (from-to)217-221
JournalInformation Processing Letters
Volume62
Issue number4
DOIs
Publication statusPublished - 1997

Fingerprint

Dive into the research topics of 'A polynomial-time algorithm for knapsack with divisible item sizes'. Together they form a unique fingerprint.

Cite this