a + 2b + 5c + 10d + 20e + 50f + 100g + 200h = 200

Where 1,2,5,10,20,50,100,200 are the values of the various types of coins. I had some meetings to go to, so I wrote a brute force solution (in Ruby) and let it run. I got back an hour later, and it was still running. I felt quite stupid. I then came up with a much better solution using some dynamic programming and recursion. It ran in 0.23s. Here it is:

def solve(n,coefficients)

x = coefficients.pop

if (coefficients.length == 0)

if (n % x == 0)

return 1

else

return 0

end

else

d = (n/x).to_i

cnt = 0

0.upto(d){|y|

xc = coefficients.collect{|p| p} #must copy since we pop array

cnt += solve(n-x*y,xc)

}

return cnt

end

end

c = [1,2,5,10,20,50,100,200]

n = 200

puts solve(n,c)

## 6 comments:

Good algorithm! When your solution takes time to compile or execute, the only problem is that your algorithm to solve the problem is slow. Recursive algorithm must be made and use some functions that are predefined or available in the programming language that you are using to run the program faster. I prefer to use those advance programming language because hey have lots of available functions and you don't need to make your own function.

Nice post! good algorithm. It is more faster to run a program when you use recursive algorithm rather than a iterative algorithm or solution.

Yes, an iterative solution usually has better performance than a recursive one. I welcome other folks to post their own solutions, in Ruby or any other programming language they like.

My first cut Java solution:

int solve(int total, int[] coefs)

{

if (total == 0) return 1;

if (total < 0) return 0;

int num = 0;

for (int value : coefs)

{

num += solve(total - value, coefs);

}

return num;

}

I wasn't completely sure why you needed to manipulate the array of coefficients, except for perhaps an optimization.

Having said that, I don't know (with a capital K) that my solution above works.

I don't think that solution works. I tried it for n=5 and c=[1,2], i.e. solutions to a + 2b = 5. It gave 8, but there are clearly only 3 solutions (1,2), (3,1), and (5,0).

After reading your blog, I came to know how these

assignment helpservices are making the work easier for a large portion of students in the world. However, there is one such website who I personally prefer goes by the name of My Assignment Services. They are the indeed the problem solver whenever I took theirNursing assignment help Australia. They are the experts when it comes to do any assignment writing; be it essays of 200 words or even dissertations of 20000 words. The most surprising thing that I come across is that they are offeringNursing case study helpat 25% discounted rates so as to make the students understand those complex case study assignments. That is why, my personal preference goes to My Assignment Services and their section of Nursing assignment help Australia.Post a Comment