𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A relation between the knapsack and group knapsack problems

✍ Scribed by Nan Zhu

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
888 KB
Volume
87
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we investigate a relation between the equality constrained Knapsack and Group Knapsack problems. This relation concerns the periodicity of optimal solutions of the Knapsack problem. We study the smallest integer b* such that for every b > b*, the Knapsack problem of size b is equivalent to the Group Knapsack problem. The results can be regarded as generalizations of some well-known results on the Frobenius problem of Number Theory. Two examples are provided to illustrate our results. A Dynamic Programming algorithm, i.e. an extended Greenberg's algorithm, is provided. Computational experiments show that this algorithm is efficient for finding b* and solving randomly generated Knapsack problems.

πŸ“œ SIMILAR VOLUMES

Factoring Polynomials and the Knapsack P
Factoring Polynomials and the Knapsack Problem
✍ Mark van Hoeij πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 222 KB

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f . This exponential time complexity is due to a com