Понимание проекта Эйлера # 31

Question

Может ли кто-нибудь объяснить мне проблему 31 проекта Эйлера ? Я не понимаю проблему ясно.

Проблема в том, чтобы вычислить монеты в любом порядке, например:

2 * £ 1 или, возможно, 1 × £ 1 + 1 × 50p + 2 × 20p + 1 × 5p + 1 × 2p + 3 × 1p ?

Answer 1

У меня тоже были проблемы с пониманием этой проблемы, я не привык к британской валюте.

В фунте 100 пенсов. Доступны следующие монеты (в пенсах): 1, 2, 5, 10, 20, 50, 100 и 200.

Вас спрашивают, сколько разных способов вы можете объединить эти значения, чтобы создать 200 пенсов.

Например, есть 4 способа сформировать 5 пенсов:

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

Удачи!

Answer 2

Вы должны разбить эту проблему на вопрос о том, сколько способов вы можете сделать каждую монету достоинством монет с одинаковыми или меньшими значениями. Это привело бы вас к чему-то вроде этого ( Я надеюсь, что мои предположения верны ):

• 1р

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

• 2р

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

• 5р

  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 3

Эй, простой дп, использующий 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 4

Это хитрое решение, которого я совсем не понимал. Решение в http://blog.csdn.net/No_End_Point/archive/2009/06/26/4301149.aspx

А вот хороший кусок теории: Целочисленный раздел в Википедии .

Отсюда: http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html

Answer 5

Эта проблема является частным случаем очень известной проблемы, называемой Subset Sum (http://en.wikipedia.org/wiki/Subset_Sum)

)

Answer 6

Я думал, что постановка проблемы ясна. Он перечисляет монеты как:

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

Как таковое, это ясно о стоимости фунта с точки зрения пенсов. Я думаю, что вопрос больше о конечной цели проблемы. Спрашивает

«Сколько можно заработать £ 2, используя любое количество монет?»

Беспорядок здесь, кажется, о порядке. Решив эту проблему, я скажу, что порядок не имеет значения в решении. Все, что имеет значение, - это количество монет каждого номинала, необходимое для того, чтобы составить в общей сложности 200 пенсов.

Я добавлю предложение, что это небольшая проблема, очень разрешимая с помощью простой рекурсии. Если вы не знаете, как поступить, вам стоит обратиться к теории разбиений числа.

Answer 7

Вы можете использовать рекурсию, чтобы рассмотреть всю сумму, которая меньше £ 2. (а затем добавить разницу как пенсы)

Answer 8

Вопрос в основном в том, сколько возможных комбинаций есть, чтобы получить 2 £ денег (= 200p), когда у вас есть 8 различных типов монет.

Вот лишь несколько (тривиальных) возможных комбинаций:

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

Вопрос в том, сколько таких комбинаций возможно?

Answer 9

Менее эффективен, чем DP, но работает в 1/2 секунды для этой конкретной проблемы. Простая рекурсия:

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