Soyo

## Problem

Just curious about how ATM works. Example, we provide it set of denominations `{10k, 20k, 50k, 100k, 200k, 500k}` about `500` papers for each.
How to program ATM to serve customer efficiently? which mean as much as possible number of withdrawer until it's out of money.

## Approach

We needs to find all ways to permit cash, then pick the suitable one. There are some idea:

• Always return minimum amount of papers, eg: use only one `500k` for `500k` withdrawal.
• Return maximum denominations with minimum amount of papers, eg: for `500k `withdrawal, return `{10k, 20k x 2, 50k, 100k x 2, 200k x 1}`.
• Average amount of papers, eg: for 500k, max papers is `10k x 50`, min is `500k x 1`, so pick the way with amount of paper nearest `25`.

Okay let's try to dig out above approaches.

## Idea 1

Let's take a look at basic DP programming problem, coin changing.

Finding the minimum number of coins, of certain denominations, required to make a given sum.

We divide it to smaller problems:

• Selecting the highest possible coin: The subproblem is about making the amount `(sum - the coin we added)` with the same set of coins.

• Ignoring the highest possible coin: In this case, the subproblem is making the same sum with the original set of coins, minus the highest possible coin.

``````func coinsChange(_ coins: [Int], _ sum: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: sum + 1), count: coins.count + 1)

// There are no result for -1 sum
for i in 0...sum {
dp[i] = Int.max
}

for i in 1...coins.count{
dp[i] = 0
}

for i in 1...coins.count {
for j in 1...sum {
if(coins[i - 1] <= j) {
dp[i][j] = min(1 + dp[i][j - coins[i - 1]], dp[i - 1][j])
} else {
dp[i][j] = dp[i - 1][j]
}
}
}

return dp[coins.count][sum]
}
``````

Our problem is similar, but need to return the list of denominations.

(cont)