Problem in understanding problem 31 of Project Euler?

Question

Hi,

Could anyone please explain me problem 31 of project euler more clearly please. My English is not good, I really don't understand problem clearly.

Is the problem saying to calculate the coins in any order like:

2*£1 or perhaps 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

Thanks in advance for your time and suggestion.

Answer 1

I had problems understanding this problem as well, not being used to British currency.

There are 100 pence in a pound. The following coins (in pence) are available: 1, 2, 5, 10, 20, 50, 100 and 200.

You are asked in how many different ways you can combine these values to create 200 pence.

As an example, there are 4 ways to form 5 pence:

• 1, 1, 1, 1, 1
• 1, 1, 1, 2
• 1, 2, 2
• 5

Good luck!

Answer 2

The question is basically how many possible combinations are there to get 2£ worth of money (= 200p) when you have the 8 different types of coins available.

Here are just a few (trivial) possible combinations:

• 1 x 2£
• 2 x 1£
• 200 x 1p
• 1 x 1£ + 100 x 1p
• ...

The question is: how many such combinations are possible?

Answer 3

You could use recursion to consider all the amount which are less that £2. (and then add the difference as pence)

Answer 4

I thought the problem statement was clear. It lists the coins as:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p)

As such, it is clear about the value of a pound in terms of pence. I think the question is more about the eventual goal of the problem. It asks

"How many different ways can £2 be made using any number of coins?"

The confusion here seems to be about order. Having solved this problem, I will state that order is unimportant in the solution. All that matters is the number of coins of each denomination required to make up the total of 200p.

I'll add the suggestion that this is a small problem, very solvable with simple recursion. If you are unsure about how to proceed, a place to look is in the theory of the partitions of a number.

Answer 5

You have to break this problem down into the question of how many ways you can make each coin value with coins of the same or lower values. This would lead you to something like this (I hope my assumptions are correct):

• 1p

  A_1p = {{1p}}
  |A_1p| = 1
  

• 2p

  A_2p = {{2p}, {1p,1p}}
  |A_2p| = 1 + 1 = 2
  

• 5p

  A_5p = {{5p}, {2p,2p,1p}, {2p,1p,1p,1p}, {1p,1p,1p,1p,1p}}
  |A_5p| = 1 + 3 = 4
  

• 10p

  A_10p = {{10p},
           {5p,5p}, {5p,2p,2p,1p}, {5p,2p,1p,1p,1p}, {5p,1p,1p,1p,1p,1p},
           {2p,2p,1p,2p,2p,1p}, {2p,2p,1p,2p,1p,1p,1p,}, {2p,2p,1p,1p,1p,1p,1p,1p,},
           {2p,1p,1p,1p,2p,1p,1p,1p,}, {2p,1p,1p,1p,1p,1p,1p,1p,1p},
           {1p,1p,1p,1p,1p,1p,1p,1p,1p,1p},
           {2p,2p,2p,2p,2p,2p}
          }
  |A_10p| = 1 + 10 + 1 = 12
  

• …

Answer 6

This problem is a special case of a very well known problem called Subset Sum (http://en.wikipedia.org/wiki/Subset_Sum)

Answer 7

this is a tricky solution that i didn't understand at all blog [dot] csdn [dot] net/No_End_Point/archive/2009/06/26/4301149.aspx

and here a good piece of theory: Integer_partition in wikipedia

from here: http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html