The problem of making change is solved

Today we're sharing a question that we're all happy about - thethe problem of making change。

Why do you say it will be happy to see it? This does not want to be more well, have talked to you about money, still need to say anything more.

Speaking of money, let's skip the small talk and get right to what we're sharing today.

This article will use thegreedy algorithm respond in singingdynamic programming If you don't quite understand it, you can check the content of these two algorithms on your own, or we'll do a share about it afterward.

Let's first look at how to usegreedy algorithmto solve. and when it can be solved using the greedy algorithm.

1. Solving the greedy algorithm

Chestnuts 🌰:

Assuming that there are currently1、2、5、10、20、50、100 Equal denomination bills, please use the least number of bills to make change.

Problems like this problem of finding zero can be solved using the greedy algorithm, since the sum of all the antecedent terms will not exceed the current element.

As:

1 + 2 < 5

1 + 2 + 5 < 10

1 + 2 + 5 + 10 < 20

Code Example:

function minCount(amount) {
  let values = [1,2,5,10,20,50,100]
  let result = 0

  while(amount) {
    amount -= values.filter(item => item <= amount).pop()
    result++
  }
  return result
}

(of a computer) run

Code Explanation:

First iterate through all possible elements and get the maximum value closest to the current change.
Decrement the current amount of money, each time decrementing the result of the+1, until the amount of money needed is0

2. Applicabledynamic programmingpresent situation

Chestnuts 🌰:

Suppose the current bill amount is only1,5,11These three, such that we can't obtain an optimal solution by applying greed in this case. The reason is as follows:

The amount of change that needs to be made is $15. If the greedy algorithm above is used, the11,1,1,1,1 This combination.

In fact, all we need is the5,5,5Three bills are OK.

So, we turned on the big change, abandoned the greedy algorithm, and solved the problem through dynamic programming.

2.1 Dynamic Programming First Edition

let values = [1,5,11]
function minCoins (amount) {
  let min = amount

  if (amount < 1) {
    return 0
  }
  if (values.includes(amount)) {
    return 1
  }

  // Find all values in values that are less than amount.
  let middle = values.filter(item => item < amount)

  for (let i = 0,len = middle.length; i < len; i++) {
    // The 1 here is equivalent to finding one first and then continuing with the rest of the amount.
    let newMin = 1 + minCoins(amount - middle[i])
    if (newMin < min) {
      min = newMin
    }
  }
  return min
}
minCoins(15) // 3

(of a computer) run

Code Parsing:

If the current amount is less than1 No change is required to return the0
If the current amount exists in the list of bills, indicating that only one is needed, return the1。
is not in the list and is not less than1 The situation:
- Find a list of bills less than the amount
- Trying to retrieve a bill
  - (Code1 + minCoins(amount - middle[i])hit the nail on the head1 This content.)
- Continue to recursively calculate the remaining amount, the minimum amount needed.
  - (Code1 + minCoins(amount - middle[i])hit the nail on the headamount - middle[i] This content.)
- If the minimum value obtained is less thanmin then updatemin(be) worth
- Returns the currently obtained minimum value.

This solution above in the implementation of the process you will find a problem, even if the current amount of previously done calculations, the next time there is the same amount of time still need to be recalculated, so there is an additional layer of computational consumption.

The solution is also very simple, justCache the results of each calculationJust come down.

2.2 Dynamic Programming Second Edition

let values = [1,5,11]
let cache = [] // Cache previous results
function minCoins (amount) {
  let min = amount

  if (amount < 1) {
    return 0
  }
  if (values.includes(amount)) {
    return 1
  }
  if (cache[amount]) return cache[amount] // If there is a cache, get the cached result directly

  let middle = values.filter(item => item < amount)

  for (let i = 0,len = middle.length; i < len; i++) {
    let newMin = 1 + minCoins(amount - middle[i])
    if (newMin < min) {
      min = newMin
    }
  }
  cache[amount] = min // Cache the currently calculated minimum value.
  return min
}

(of a computer) run

Here is where the smallest most of our calculations are cached.

Check to see if the minimum number of bills for this amount is cached before each solution.

If the cache is hit, the contents of the cache are returned directly.

Well, the above is what we have shared this time. I hope that the content of this sharing can bring you help yo.

See you next time, bye.