here is simple way to do it..:
A[1000] //1000 is maximum formadable sum can be provided..
S is set of coins that you have,K is the sum to be formed
initialize the array A by larege value
for(x in S):
A[x]=1
for 0<i<1000
for 0<j<1000
if(i+j<1000 && A[i]+A[j]<A[i+j] )
A[i+j]=A[i]+A[j]
return A[K]
On Sat, Apr 10, 2010 at 6:27 PM, Rohit Saraf
<rohit.kumar.sa...@gmail.com> wrote:
> What do u mean by "y u need backtracking "
> DP needs backtracking to reconstruct the solution.
> -Rohit
>
>
>
> On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra <amishra....@gmail.com>
> wrote:
>>
>> y u need backtracking
>> i think it can be done with DP
>>
>> On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» <anujlove...@gmail.com> wrote:
>>>
>>> Need help in designing efficient backtracking algorithm for the coin
>>> changing problem. where a1, a2, an are the set of distinct coins
>>> types, where each ai is an integer. and each type is unlimited
>>> quantity.
>>>
>>> the problem to make up the exact amount C using minimum total number
>>> of coins. use backtracking template with a bounding function..
>>>
>>> help appreciated......
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> How soon 'not now' becomes 'never'...
>>
>> --
>> 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.
>
> --
> 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.
>
--
~~~~BL/\CK_D!AMOND~~~~~~~~
--
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.
