1
$\begingroup$

As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible combinations. Instead we need only to determine if a certain subset of coins of same or varying denomination, equal exactly to, some amount M.

My recursion equation of the problem is as follows:

let k = 0

If ∑ (v1 + v2 + … + vn) = M   
    return true

If ∑ (v1 + v2 + … + vn) < M
    return false

Else 
    Increment k by 1
    make recursive call on coin subset {v1, v2, … v(n-k)}

The next question is to convert this into pseudo-code that represents a dynamic programming solution to this problem.

I'm a bit stuck. If you were to make a table of every possible sum {v1 + v2}, {v1 + v2 + v3}, {v1 + v2 + v3 + v4}, etc. You could eventually find a solution but wouldn't that be a much less efficient brute force approach?

I assume the solution would include some implementation of memoization or some way to store and retrieve sums already encountered, but being that the problem is not an optimization problem, I'm having a hard time envisioning a dynamic solution.

Much of the dynamic programming examples that I see suggest iteratively subtracting elements, one item at a time, which is similar to the composition of my recursion equation but I don't see a modification that would make this pseudo code dynamic in nature.

If anyone could please enlighten me, I'd be very grateful

$\endgroup$
6
  • $\begingroup$ @Apass.Jack No, in this example the values are indeterminate $\endgroup$ Mar 8, 2019 at 4:24
  • 1
    $\begingroup$ What will be the input of the program or algorithm? Are they $n$, $v_1, v_2, ..., v_n$ and $M$? There are infinitely many coins in some setup. $\endgroup$
    – John L.
    Mar 8, 2019 at 4:39
  • $\begingroup$ @Apass.Jack thank you for taking the time. My understanding is that $M$ would be some given integer that represents a value which we wish to determine if we have enough change to afford exactly without overpaying. ${v1, v2, v3, ... vn}$ would represent a set of $n$ individual coins, some of which have different denominations. $vn$ would simply denominate the last coin in the set, and $v(n-1)$ would be the second to last. I'm guessing that the solution may require the set of coins to be in sorted order $\endgroup$ Mar 8, 2019 at 4:57
  • 1
    $\begingroup$ Is my answer helpful and good enough? $\endgroup$
    – John L.
    Mar 15, 2019 at 3:43
  • $\begingroup$ @Apass.Jack it certainly is, thank you so much for taking the time to assist a struggling student. $\endgroup$ Mar 16, 2019 at 0:04

1 Answer 1

1
$\begingroup$

Given an integer $M>0$ and $n$ coins with integer values $v_1, v_2,\cdots, v_n$, where $M, n, v_i$ are positive, how can we determine if some of the coins can add up to $M$?

This problem is a common version of subset sum problem. There are many strategies to solve the problem.


Here is the pseudocode by dynamic programming that is about as simple as possible.

  • Let $s$ be an array of size $M+1$ with default value 0 and starting index 0. Let $s[0]=1$.
  • For $i$ from 1 to $n$, do:
    • For $j$ from 0 to $M$, do:
      • If $s[j]=1$, let $s[j+v_i]= 1$.
  • If $s[M]=1$, return yes. Otherwise, return no.

Here is an example to illustrate the algorithm. Let $M=7$. Coins are $1,3,3,5$.

  • $s=[1,0,0,0,0,0,0,0]$.
  • Here are $s$ at the end of each iteration.
    • $s=[1,1,0,0,0,0,0,0]$
    • $s=[1,1,0,1,1,0,0,0]$
    • $s=[1,1,0,1,1,0,1,1]$
    • $s=[1,1,0,1,1,5,1,1]$
  • return yes since $s[7]=1$

We can optimize the algorithm above in various ways.

  • We can stop the algorithm once we have found $s[M]=1$.
  • We can change $s$ to a double linked-list, whose elements are the realizable values in increasing order.
  • We can split the given array of values to two arrays of equal size or sizes with difference 1. Run the algorithm on each of two arrays. Check if we can select one number from each resulting array $s$ such that their sum is $M$, using two-pointer technique.
  • This last item means all other ways, as always.

Exercise. Adapt the algorithm so that it also tells the least number of coins used if the answer is yes.

$\endgroup$
1
  • 1
    $\begingroup$ Another simple optimization is to compute of the maximum realizable value in the end of each iteration, which will be the upper limit of $j$ in the next iteration. $\endgroup$
    – John L.
    Mar 9, 2019 at 20:17

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.