[Solved]: Find the coins required which sum to S

Problem Detail: 

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once).

I was recently studying the very same problem from topcoder.com but there "we can use each coin any number of times". I am just stuck here if we can use each coin only once and not multiple times.

It will be very helpful if you can help or just give a hint. (this is not my homework quiz :P)

Asked By : Prashant Yadav

Answered By : jonaprieto

This is a classic problem in dynamic programming, so you could review in literature a nicely description, search for the subset sum problem. With that problem the set is the values of coins, and you're looking for a subset that sum exactly $S$. (a subset is the answer).

The first, it's know it's exists such subset and it could find with the first version of subset-sum algorithm using dynamic programing as I show after with the recursive relation $f$. Then, we have to modify a little the algorithm to construct the solution (the subset of coins) using recursion maybe or other method.

The recursive relation to this problem with bases cases defined is:

$$ f(k, S) = Or \begin{cases} f(k -1, S) & \text{Case #}1\\ f(k-1, S - V_{k}) & \text{Case #}2\ \ S\geq V_{k} \end{cases} $$

• Case #1: it's possible to get $S$ with first $k-1$ coins ?
• Case #2: coin $V_{k}$ it's taken. So it's possible to get the rest, i.e. $S - V_{k}$ with the first $k-1$ coins?

Note: Sure about the base cases. I mean $f(k, 0) = False$, $f(0, 0)=True$, and others.

To construct the coins to sum $S$. You got to remember which of cases for $f$ were True, because the first says, don't to need $V_k$, and the second case do.

The algorithm looks like more or less:

If $f(N, S)$ is True. You ask it's $f(N-1, S)$ is True. If it's True, you don't need to put $V_N$ in the solution. If it's False, $f(N-1, S- V_N)$ should be True, so, you need to put get in to it. And so on until you'd finished to consider the N coins or you've finished before looking for a sum zero.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33943

3.2K people like this

 Download Related Notes/Documents