Понимание алгоритма изменения

Ответ 1

Чтобы получить все возможные множества, что элементы равны "a" или "b" или "c" (наши монеты), которые суммируются до "X", вы можете:

• Возьмем все такие множества, которые суммируются с X-a и добавим к ним дополнительный "a".
• Возьмем все такие наборы, которые суммируются с X-b и добавим к ним дополнительный "b".
• Возьмем все такие множества, которые суммируются с точностью до X-c и добавят к ним каждый дополнительный c.

Таким образом, количество способов, которыми вы можете получить X, - это сумма чисел, с помощью которых вы можете получить X-a и X-b и X-c.

ways[i]+=ways[i-coin]

Отдых - это простое повторение.

Дополнительный намек: в начале вы можете получить набор с нулевой суммой одним способом (пустой набор)

ways = [1]+[0]*target

Ответ 2

Это классический пример динамического программирования. Он использует кэширование, чтобы избежать ошибок при подсчете таких вещей, как 3 + 2 = 5 дважды (из-за другого возможного решения: 2 + 3). Рекурсивный алгоритм попадает в эту ловушку. Давайте сосредоточимся на простом примере, где target = 5 и coins = [1,2,3]. Размещенный вами код имеет значение:

1. 3 + 2
2. 3 + 1 + 1
3. 2 + 2 + 1
4. 1 + 2 + 1 + 1
5. 1 + 1 + 1 + 1 + 1

в то время как рекурсивная версия имеет значение:

1. 3 + 2
2. 2 + 3
3. 3 + 1 + 1
4. 1 + 3 + 1
5. 1 + 1 + 3
6. 2 + 1 + 2
7. 1 + 1 + 2
8. 2 + 2 + 1
9. 2 + 1 + 1 + 1
10. 1 + 2 + 1 + 1
11. 1 + 1 + 2 + 1
12. 1 + 1 + 1 + 2
13. 1 + 1 + 1 + 1 + 1

Рекурсивный код:

coinsOptions = [1, 2, 3]
def numberOfWays(target):
    if (target < 0):
        return 0
    elif(target == 0):
        return 1
    else:
        return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)

Динамическое программирование:

target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin, target+1):
        ways[i]+=ways[i-coin]
print ways[target]

Ответ 3

Основная идея кода заключается в следующем: "На каждом шаге есть ways способы внести изменения в сумму i при выплате монет [1,...coin]".

Итак, на первой итерации у вас есть только монета с наименованием 1. Я считаю, что очевидно, что есть только один способ дать изменение, имеющее только эти монеты для любой цели. На этом шаге ways массив будет выглядеть как [1,...1] (только один путь для всех целей от 0 до target).

На следующем шаге добавим монету с наименованием 2 к предыдущему набору монет. Теперь мы можем подсчитать, сколько комбинаций изменений для каждой цели от 0 до target. Очевидно, что количество комбинаций будет увеличиваться только для целей >= 2 (или добавлена ​​новая монета в общем случае). Таким образом, для цели равна 2 количество комбинаций будет ways[2](old) + ways[0](new). Как правило, каждый раз, когда i равна новой введенной монете, нам нужно добавить 1 к предыдущему числу комбинаций, где новая комбинация будет состоять только из одной монеты.

Для target > 2 ответ будет состоять из суммы "всех комбинаций суммы target, имеющей все монеты меньше coin", и "все комбинации суммы coin, имеющие все монеты меньше coin сам".

Здесь я описал два основных шага, но я надеюсь, что это легко обобщить.

Позвольте мне показать вам вычислительное дерево для target = 4 и coins=[1,2]:

пути [4] для монет = [1,2] =

пути [4], указанные монеты = [1] + пути [2], данные монеты = [1,2] =

1 + пути [2] заданы монеты = [1] + пути [0] с учетом монет = [1,2] =

1 + 1 + 1 = 3

Итак, есть три способа дать изменение: [1,1,1,1], [1,1,2], [2,2].

Приведенный выше код полностью эквивалентен рекурсивному решению. Если вы понимаете рекурсивное решение, я уверен, вы понимаете решение, приведенное выше.

Ответ 4

Решение, которое вы опубликовали, представляет собой обобщенную версию этого кода.

    /// <summary>
    /// We are going to fill the biggest coins one by one.
    /// </summary>
    /// <param name="n"> the amount of money </param>
    public static void MakeChange (int n)
    {
        int n1, n2, n3; // residual of amount after each coin
        int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c
        for (quarter = n/25; quarter >= 0; quarter--)
        {
            n1 = n - 25 * quarter;
            for (dime = n1/10; dime >= 0; dime--)
            {
                n2 = n1 - 10 * dime;
                for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--)
                {
                    n3 = n2 - 5 * nickel;
                    Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent.
                }
            }
        }
    }