1
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hint: Dynamic programming on this subproblem: "Can I get a sum of $x$ if I can use only the $k$ smallest coins?"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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