Unbounded knapsack problems with arithmetic weight sequences |
| |
| Authors: | Vladimir G Deineko |
| |
| Institution: | a Warwick Business School, The University of Warwick, Coventry CV4 7AL, United Kingdom
b Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands |
| |
| Abstract: | We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances. |
| |
| Keywords: | Combinatorial optimization Computational complexity Dynamic programming Polynomially solvable special case |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
