Cashier Machine Using Basic Knapsack Algorithm

Elementary greedy algorithm used by cashiers all over the world millions of times per day.

This is a C++ implementation of coin cashier machine algorithm to return minimum number of coins that add up to the total denomination given.

Target Complexity : O(n)

Problem Description

The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Input Format. The input consists of a single integer 𝑚.

Constraints. 1 ≤ 𝑚 ≤ 103.

Output Format. Output the minimum number of coins with denominations 1, 5, 10 that changes 𝑚.