An application of an optimal behaviour of the greedy solution in number theory (Q1321639)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An application of an optimal behaviour of the greedy solution in number theory |
scientific article; zbMATH DE number 558687
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An application of an optimal behaviour of the greedy solution in number theory |
scientific article; zbMATH DE number 558687 |
Statements
An application of an optimal behaviour of the greedy solution in number theory (English)
0 references
2 June 1994
0 references
The Frobenius problem of finding the largest integer that is not representable by \(\sum^ n_{i=1} a_ ix_ i\), gcd \((a_ 1,a_ 2, \dots, a_ n)=1\), \(x_ i\) nonnegative integers is handled by the greedy algorithm for knapsack problems. Some new upper bounds and exact solutions of subproblems are provided. These methods seem to be a new unified way in treating the Frobenius problem.
0 references
linear diophantine equation
0 references
Frobenius problem
0 references
greedy algorithm
0 references
knapsack problems
0 references
upper bounds
0 references
exact solutions of subproblems
0 references
