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
<[email protected]> 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 <[email protected]>
> wrote:
>>
>> y u need backtracking
>> i think it can be done with DP
>>
>> On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» <[email protected]> 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 [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.
>>>
>>
>>
>>
>> --
>> 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 [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.
>
--
~~~~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 [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.
