An application of an optimal behaviour of the greedy solution in number theory (Q1321639)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An application of an optimal behaviour of the greedy solution in number theory |
scientific article |
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
