Understanding the Euler Project # 31

Question

Can someone explain to me problem 31 of the euler project ? I do not understand the problem clearly.

The problem is to calculate coins in any order, for example:

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

Answer 1

I had problems understanding this problem, not the British currency.

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

You are asked 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

!

Answer 2

, 2 (= 200p), 8 .

() :

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

: ?

Answer 3

, , , £ 2. ( )

Answer 4

, . :

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

, . , .

" 2 ?"

, , . , , . , , - , 200p.

, , . , , , , .

Answer 5

, . - ( , ):

• 1p

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

• 2

  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

Sum (http://en.wikipedia.org/wiki/Subset_Sum)

Answer 7

This is a difficult decision that I did not understand at all. The solution is at http://blog.csdn.net/No_End_Point/archive/2009/06/26/4301149.aspx

And here's a good theory: the Integer section on Wikipedia .

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

Answer 8

Hi simple dp using python:

ways = [0]*201
ways[0] = 1
for x in [1,2,5,10,20,50,100,200]:
    for i in xrange(x, 201):
        ways[i] += ways[i-x]
print ways[200]

Answer 9

Less effective than DP, but works in 1/2 second for this particular problem. Simple recursion:

solve    []     s         = 0

solve    (c:ct) 0         = 1

solve    (c:ct) s | c > s = solve ct s

solve cs@(c:ct) s         = (solve cs (s - c)) + (solve ct s)

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