Optimal and canonical solutions of the change making problem

DOI10.1016/0377-2217(80)90143-5zbMath0436.90075OpenAlexW1965966338MaRDI 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 analysiscomputational efficiencyheuristic algorithmoptimal solutionsingle knapsack problemGreedy algorithmbranch-decision treecanonical solutionschange making problemcutting-stock problemsdepth-first branch and bound algorithmdetermination of lower boundstrong dominance criterionuni-dimensional cargo-loading

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Specification and verification (program logics, model checking, etc.) (68Q60)

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