0
$\begingroup$

According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.

The problem is such:

You are required to give change equal to n (n is a positive nonzero integer, not necessarily bigger than biggest coin) with a given set of k different coins such that each coin has a positive nonzero “value”.

The problem is to find the combination with least amount of coins that is equal to n.

The only method of solution I can come up with is the 'brute' approach, so if I have the set {k1,k2,k3} of coins, I'll need to calculate f(n-k1), f(n-k2), f(n-k3) and for each of f(n-k_i) I'll have to calculate another 3 possibilities, which lead to exponential complexity.

However, I've read that this is possible to solve in O(n) time, yet all explanations I've seen were really math-based and non-intuitive.

I’m really eager to understand this solution, so any source of information regarding this problem could assist in many ways.

Thanks!

$\endgroup$
2
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Jun 2, 2022 at 4:28
  • 1
    $\begingroup$ "I’m really eager to understand this solution": you have described the problem, but not the particular solution. So how could we help ? $\endgroup$
    – user16034
    Jun 2, 2022 at 19:32

2 Answers 2

2
$\begingroup$

This problem is similar to the Knapsack problem. The only difference is that in your case you need to minimize (the amount of coins) instead of maximize (the amount of items in the bag).

The problems are very similar, I think you can get the solution alone :)

$\endgroup$
5
  • $\begingroup$ I found the problem I’m asking about in Wikipedia, however I still can’t seem to comprehend how this is done in most efficient time. Care to share a more intuitive explanation? $\endgroup$
    – Aishgadol
    Jun 2, 2022 at 9:18
  • $\begingroup$ Can you link the Wikipedia page you're referring to? Also, elaborate your question about time complexity more. Are you struggling to comprehend how this algorithm is better than the "brute force" one? $\endgroup$
    – Pietro
    Jun 2, 2022 at 15:04
  • $\begingroup$ this is the link: en.wikipedia.org/wiki/Change-making_problem If i'm not wrong, the brute force (is that also the greedy approach?) simply starts with n, then tries to apply each coin such that f(n)=f(n-c)+1, afterwards, for each different coin it deducted, it then tries to deduct another coin, so this becomes exponential complexity, while the problem (according to the study materials I was given) is solveable in o(n) time. $\endgroup$
    – Aishgadol
    Jun 3, 2022 at 9:08
  • $\begingroup$ I suggest reading this: geeksforgeeks.org/…. It is well written. Try to understand the examples and you'll be fine! $\endgroup$
    – Pietro
    Jun 3, 2022 at 9:49
  • $\begingroup$ Thank you for your assistance, I'll try to make the most out of the link. $\endgroup$
    – Aishgadol
    Jun 3, 2022 at 9:50
0
$\begingroup$

You are on the right track that, given a change amount $n$ and denominations $k_1, k_2, k_3$, to compute the minimum number of coins $f(n)$ for change amount $n$ you need to compute $f(n-k_1)$, $f(n-k_2)$ and $f(n-k_3)$.

The main objective is to derive a recursive equation for $f(n)$. Imagine you are given the minimum number of coins for change amount $n$, one coin at a time. In the last step, there are three cases for the value of the last coin: the coin had value $k_1$, and that before that step the change amount $n-k_1$ was given to you optimally, i.e. using $f(n-k_1)$ coins, for a total of $f(n-k_1)+1$ coins. Similarly for the other two cases. This gives the recursive equation $f(n) = min\{f(n-k_1), f(n-k_2), f(n-k_3)\}+1$.

Now that we have a recursive equation for $f(n)$, we can implement it using top-down recursion. To compute $f(n)$ in linear time, you can store the values of smaller subproblems $f(n-k)$ for various $k$ in a table $T$ (stored as a dictionary in the pseudocode below) before returning its value, so that each subproblem is solved only once. This method is called top-down recursion with memoization. Here's the pseudocode:

function f(n):
    if n = 0 then return 0
    if n in {k_1, k_2, k_3} then return 1
    if n in T then return T[n] #since subproblem was solved previously, just do a lookup
    else #need to compute and store T[n] before returning a value
        temp = min{f(n-k_1), f(n-k_2), f(n-k_3)} + 1
        T[n] = temp  #memoization: store solution to subproblem before returning solution
        return T[n]


    
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.