A POLYNOMIAL-TIME ALGORITHM FOR KNAPSACK WITH DIVISIBLE ITEM SIZES

Authors
VERHAEGH WFJ AARTS EHL
Citation
Wfj. Verhaegh et Ehl. Aarts, A POLYNOMIAL-TIME ALGORITHM FOR KNAPSACK WITH DIVISIBLE ITEM SIZES, Information processing letters, 62(4), 1997, pp. 217-221
Citations number
4
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
62
Issue
4
Year of publication
1997
Pages
217 - 221
Database
ISI
SICI code
0020-0190(1997)62:4<217:APAFKW>2.0.ZU;2-I
Abstract
We consider the special case of the bounded knapsack problem with divi sible item sizes, and present an algorithm that solves it in polynomia l time. The main characteristic of the algorithm is the fact that it h andles the items in order of increasing size, in contrast to known pol ynomial algorithms for the unbounded knapsack problem. (C) 1997 Elsevi er Science B.V.