use dynamic programming to solve this problem :-
here is the algo:-
result[S];
result[0]=1;
index;
for i=0 to len(coins[])
c=coins[i];
for k=c to S
index=k-c;
result[k]= result[k] + result[index];
end
end
print result[S];
On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta <[email protected]> wrote:
> Given a list of N coins, their values (V1, V2, ... , VN), and the
> total sum S. Find the minimum number of coins the sum of which is S
> (we can use as many coins of one type as we want), or report that it's
> not possible to select coins in such a way that they sum up to S.
>
> For a better understanding let's take this example:
> Given coins with values 1, 3, and 5.
> And the sum S is set to be 11.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
