If the sum needed S, is small .. then we can do a straight forward DP as
follows,
// given array A of coin values and its size is 'm' and sum needed S
initialize array 'dp' to some big value , say INF
dp[0] = 0;
for( i = 1 ; i < = S ; i ++)
{
for(j = 0; j < m ; j ++)
if ( i - A[j] > = 0 )
dp[ i ] = min ( dp[i] , 1 + dp[ i-A[j] ] ) ;
}
return dp[S]==INF ? "not possible" : dp[S];
--------
AK
On Wed, Dec 30, 2009 at 11:27 PM, vicky <mehta...@gmail.com> wrote:
> ques->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.
>
> ex:
> S=11
> coins: 1,3,5
> ans:3->(5,5,1)
>
> S=6
> coins:1,3,5
> ans:2,(3,3 or 1,5)
>
> S=20
> coins:3,6,8
> ans:3,(6,6,8)
>
> S=15
> coins:3,7,10
> ans: not possible
>
>
> --
>
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
