HàPhan 河

From Coin Change to ATM withdrawals

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[0][i] = Int.max
    }	      

    //Solution always start with 0
    for i in 1...coins.count{
        dp[i][0] = 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)

Comments