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)
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.
ReplyDeleteNice post! good algorithm. It is more faster to run a program when you use recursive algorithm rather than a iterative algorithm or solution.
ReplyDeleteYes, 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.
ReplyDeleteMy first cut Java solution:
ReplyDeleteint 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).
ReplyDelete