Optimal and canonical solutions of the change making problem

DOI10.1016/0377-2217(80)90143-5zbMath0436.90075MaRDI QIDQ1141080

Paolo Toth, Silvano Martello

Publication date: 1980

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(80)90143-5

zbMATH Keywords

performance analysis; computational efficiency; heuristic algorithm; optimal solution; single knapsack problem; Greedy algorithm; branch-decision tree; canonical solutions; change making problem; cutting-stock problems; depth-first branch and bound algorithm; determination of lower bound; strong dominance criterion; uni-dimensional cargo-loading

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C10: Integer programming

68Q60: Specification and verification (program logics, model checking, etc.)

Related Items

Knowledge based approach to the cutting stock problem, Heuristic methods and applications: A categorized survey, A typology of cutting and packing problems

Cites Work

• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• When the Greedy Solution Solves a Class of Knapsack Problems
• The Change-Making Problem
• Canonical Coin Changing and Greedy Solutions
• Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem
• Algorithmic Solution of the Change-Making Problem