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
this is dynamic programming problem. try to use dynamic programming...
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
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
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.comwrote:
y u need backtracking
i think it can be done with DP
On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »»
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 0i1000
for 0j1000
if(i+j1000 A[i]+A[j]A[i+j] )
