0

I was trying to implement a variation of the change count problem (in algorithms) where it is required to find the number of different ways you can change an amount and after much reasoning it turned out to be a maths problem. For example, if given the coins 50, 20, 100 find the number of ways to change 300

The problem is an equation of the form

ax1 + bx2 + ... + kxn = y,  a, b, ..., k and y all known and > 0

It is required to find all the possible solutions, for the set of positive integers including 0. Actually I need only the number of solutions. I'd generally think up algorithms myself but I'm not sure how to tackle this.

justhalf
  • 8,960
  • 3
  • 47
  • 74
theking
  • 87
  • 13
  • 2
    This is not functional programming, and you should use dynamic programming for this. A similar problem: https://en.wikipedia.org/wiki/Change-making_problem . You will need to change the algorithm there a bit to solve your problem. Also, do you actually need to list all possible solutions or just the number of solutions? Your title says you need to list all, but in the question you say you just need the number of solutions. Please clarify. – justhalf Apr 13 '16 at 05:35
  • 1
    If you're interested in the mathematical side of this, "Polya, How to solve it" has a good discussion. See http://stackoverflow.com/a/20743780/1400793 for an example of code using Polya's approach. – Paul Hankin Apr 13 '16 at 05:57
  • @justhalf Sorry for the confusion. Firstly I want to implement it in a functional programming language. Secondly the problem requires just the number of solutions but I want to list the solutions. – theking Apr 13 '16 at 09:30
  • I'm studying Martin Odersky's course on functional programming and loops haven't been introduced yet. So this problem is required to be solved using recursion only. – theking Apr 13 '16 at 09:48
  • @theking Ah, I see. Then I think you need to rephrase the question to indicate that you want to do this in functional programming. That said, I think it is better if you can show some attempts in doing this (see http://stackoverflow.com/help/how-to-ask). About listing the solutions, it usually requires more effort than just getting the number of solutions, so maybe you say "The task is to get the number of solutions. But I'm also interested in seeing the list of solutions, if possible.", thereby making "list the solution" as an additional point, since it requires different solution. – justhalf Apr 14 '16 at 01:33

1 Answers1

0

This is a classic dynamic programming problem.

Let a[x] be the number of ways you can pay x using the coins available.

a[0]=1 since the only way to pay 0 is to not give any coins out.

You build this up by adding coins. For each coin you need to iterate over the rage of interest (0-300) and compute a[x] = a[x] + a[x - coin] (if x>=coin).

When you are done with all the coins a[x] will be the result you want.

Sorin
  • 11,863
  • 22
  • 26