Question

Имеется 30 монет по 1 копейке, 6 монет по 5 копеек, 3 монеты по 10 копеек, 1 монета по 20 копеек. Каким числом способов из этих монет можно составить сумму в 30 копеек?​

Answer 1

Ответ: можно составить 30 копеек:

1) 30 монет по 1к=30*1=30копеек

2) 6 монет по 5к=6*5=30копеек

3) 3 монеты по 10к=10*3=30копеек.

Нельзя составить 30 копеек:

1) 1 монета по 20к=1*20=20копеек

Пошаговое объяснение:

Answer 2

Для решения данной задачи можно использовать метод динамического программирования.

Построим таблицу dp размером (31, 4). Назовем dp[i][j] количество способов составить сумму i копеек, используя первые j типов монет.

Инициализируем массив dp следующим образом:

- dp[0][j] = 1 для всех j (так как есть только один способ составить сумму 0 - не использовать ни одной монеты)

Далее заполняем таблицу dp поочередно для каждой суммы от 1 до 30 и для каждого типа монет.

Для каждой ячейки (i, j) суммируем dp[i][j-1] (количество способов, которые можно получить без использования монеты j) и dp[i-коп[j]][j] (количество способов, которые можно получить, используя монету j).

Где коп[j] это хранит значение текущей монеты типа j.

После заполнения таблицы dp, ответом на задачу будет значение dp[30][4] (количество способов составить сумму 30 копеек, используя все типы монет).

Подробнее процесс заполнения таблицы:

- Для первого типа монет (1 копейка) значение dp[1][1] = 1, а для всех dp[i][1] = 1 (так как есть только один способ составить сумму i - использовать все возможные монеты по 1 копейке).

- Для второго типа монет (5 копеек) заполняем только те ячейки, для которых i >= 5. Например, dp[5][2] = dp[5][1] + dp[0][2] = 1 + 0 = 1, так как есть только один способ составить сумму 5 - использовать одну 5-копейку.

- Для третьего типа монет (10 копеек) заполняем только те ячейки, для которых i >= 10. Например, dp[10][3] = dp[10][2] + dp[0][3] = 1 + 0 = 1, так как есть только один способ составить сумму 10 - использовать одну 10-копейку.

- Для последнего типа монет (20 копеек) заполняем только ту ячейку, для которой i = 20. Например, dp[20][4] = dp[20][3] + dp[0][4] = 1 + 0 = 1, так как есть только один способ составить сумму 20 - использовать одну 20-копейку.

Таким образом, dp[30][4] = 2, то есть есть два способа составить сумму 30 копеек, используя все типы монет.

Ответ: число способов составить сумму в 30 копеек из данных монет - 2.