Optimal bounds for the change-making problem

DOI10.1016/0304-3975(94)90134-1zbMath0801.68079OpenAlexW2037843120MaRDI QIDQ1314390

Shmuel Zaks, Dexter Kozen

Publication date: 22 February 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90134-1

zbMATH Keywords

greedy algorithmKnapsackchange-making problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorics in computer science (68R05)

Related Items

What's in \textit{YOUR} wallet? ⋮ Unnamed Item ⋮ Characterization of canonical systems with six types of coins for the change-making problem ⋮ The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves ⋮ A polynomial-time algorithm for the change-making problem ⋮ Combinatorics of the change-making problem

Cites Work

• Unnamed Item
• Heuristic algorithms for the multiple knapsack problem
• Algorithmic Solution of the Change-Making Problem