dynamic pseudo-code for simplified coin changing algorithm

Question

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

Answer 1

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.