Algorithms and Data Structures

Coin change

💡
The coin change problem is one of the most popular Dynamic Programming problems. It vividly demonstrates the contrast between the Greedy and Dynamic Programming approaches, and how one might find themselves falling into the trap of thinking that the greedy approach might be sufficient, while the greedy algorithm only arrives at a suboptimal result instead of solving the global problem.
Given a money system that consists of n coins, each coin has a positive value . You are asked to find a way to obtain a total amount of x by using as few coins as possible.
For instance, if the coin values are and we need to obtain 11, the optimal choice would be to have 1 + 5 + 5 ⇒ 3 coins.

Input

The first line of the input contains two integers n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).
The next line contains n space-separated integers (1 ≤ ≤ ).

Output

The program should print the minimal number of coins that are necessary to get x. If it is not possible to produce the desired sum x, the program should print -1.

Examples

Input
Output
3 11 1 5 7
3
3 12 1 5 7
2

Explanation

  1. 11 → 1 + 5 + 5
  1. 12 → 5 + 7
 

Tutorial

Notice that the greedy approach of always taking the largest possible coin won’t work. The first example demonstrates that quite nicely. If we want to get 11, and we first take the largest possible coin, it would be 7 ⇒ we need to get 11-7 = 4. Therefore, we need to get 4 1s, which will amount to 5 coins in total. While the actual answer is only 3 (5 + 5 + 1).
Let’s keep a state d[i] which will be the minimum number of coins required to obtain the sum i. If we’re able to properly initialize d and update all the values up to the desired sum x, the final answer would be d[x] itself (the minimum number of coins required to obtain x).
Initially, we can set all the values of d to be infinity (not possible to obtain that sum) except 0, which is possible to obtain with 0 coins:
c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] is 0 and d[1...x] inclusive is infinity
Then, for each number 1...x, we try to find the minimal number of coins required to get the number. If we have arrived at a number num, we try all the possible coins to see if we can get num by adding the value of the coin to any of the previous values obtained (num - ). If that improves the answer, we update d[num]. So, for each num in 1...x, we try to find all the possible previous states that could lead to num and try to improve the state d[num]:
for num in range(1, x + 1):       # Iterate over all the numbers 1...x inclusive
    for ci in c:                  # Try to improve d[num] with all the coins
        if num - ci >= 0:         # If it's possible to obtain num with i-th coin
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])
d[num] = min(d[num], d[num - ci] + 1) is the key point in the solution of the problem. On each iteration, we try to improve the state of d[num] if it’s possible to do so through num - . So, we take the minimal number of coins required to obtain num - and add 1 to use the coin .
When all the numbers with all the coins are processed, the final answer is just the value of d[x].
Let’s simulate the algorithm on the sample input:
c = [1, 5, 7] and x = 11
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 (try to improve the number of coins to get the sum of 1) ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 2 (try to improve the number of coins to get the sum of 2) ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 3 (try to improve the number of coins to get the sum of 3) ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 4 (try to improve the number of coins to get the sum of 4) ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 5 (try to improve the number of coins to get the sum of 5) ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞] ci = 7 ⇒ num - ci < 0
  1. num = 6 (try to improve the number of coins to get the sum of 6) ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ num - ci < 0
  1. num = 7 (try to improve the number of coins to get the sum of 7) ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
  1. num = 8 (try to improve the number of coins to get the sum of 8) ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. num = 9 (try to improve the number of coins to get the sum of 9) ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. num = 10 (try to improve the number of coins to get the sum of 10) ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞] ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞] ci = 7 ⇒ does not update
  1. num = 11 (try to improve the number of coins to get the sum of 11) ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. print(d[11]) ⇒ prints 3
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue