Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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