Question

Сколькими спасобами можно разложить 500 сумов, купюрами достоинством 100 и 200?​

Answer 1

500=100+100+100+100+100
500=100+200+200
500=100+100+100+200

Answer 2

Для решения этой задачи можно воспользоваться методом динамического программирования. Давайте создадим массив ways размером 501 (от 0 до 500), где ways[i] будет содержать количество способов разложить i сумов купюрами 100 и 200. Начнем с того, что ways[0] = 1, так как единственный способ разложить 0 сумов - не использовать купюры вообще.

Далее, для каждого значения от 100 до 500, мы будем пересчитывать количество способов, используя предыдущие значения массива ways. Если j - текущее значение (100, 200, 300, ..., 500), тогда количество способов можно посчитать следующим образом:

ways[j] = ways[j - 100] + ways[j - 200]

Это потому, что чтобы получить j сумов, мы можем взять купюру достоинством 100 и оставить j - 100 сумов, или взять купюру достоинством 200 и оставить j - 200 сумов. Суммируя эти два случая, мы получаем общее количество способов разложить j сумов.

После того как массив ways будет заполнен, ways[500] содержит искомый ответ - количество способов разложить 500 сумов купюрами 100 и 200.

Давайте рассчитаем это в коде:

pythonCopy code
ways = [0] * 501
ways[0] = 1

for i in range(100, 501):
    ways[i] = ways[i - 100] + ways[i - 200]

print(ways[500])

Запустив этот код, вы получите количество способов разложить 500 сумов купюрами 100 и 200.