Найти всевозможные комбинации монет

Question

Есть монеты, 1р 2р 5р 10р 25р 50р 100р 150р 200р. Найти всевозможные кол-во комбинаций чтоб в общей сумме было 200р Пример: 200 монеток по 1 рублю. 100 монеток по 2 р и т.п

a = [1, 2, 5, 10, 25, 50, 100, 150, 200]
b = 200
for n in range(1, len(a) + 1):
    comb = it.combinations(a, n)
    for i in comb:
        if sum(i) == b:
            print(i)'

Написал такой код, но проблема в том что он берет один элемент массива 1 раз, как сделать чтоб он брал неограниченное кол-во раз?

Answer 1

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

a = [1, 2, 5, 10, 25, 50, 100, 150, 200]
b = 200
count = 0
last_number = 1

for n in a:
    for i in a:
        result = n

        if i <= n: continue
        else: b = i

        while True:
            result += n
            count += 1

            if result == b:
                print(f'{n} по {count + 1} раз равно {b}')
                count = 0
                break
            elif result > b:
                count = 0
                break

UPD: Я исправил программу. Попробуйте новый вариант.

Answer 2

Рекурсивно - кладём монету, решаем задачу для оставшейся суммы.

def razmen(summa, nominals, lastindex=0, lst=[]):
    if summa == 0:
        print(lst)
    else:
        for i in range(lastindex, len(nominals)):
            if nominals[i] <= summa:
                razmen(summa - nominals[i], nominals, i, lst + [nominals[i]])

razmen(10, [1,2,3,5,10,15,20])

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 3]
[1, 1, 1, 1, 1, 1, 2, 2]
[1, 1, 1, 1, 1, 2, 3]
[1, 1, 1, 1, 1, 5]
[1, 1, 1, 1, 2, 2, 2]
[1, 1, 1, 1, 3, 3]
[1, 1, 1, 2, 2, 3]
[1, 1, 1, 2, 5]
[1, 1, 2, 2, 2, 2]
[1, 1, 2, 3, 3]
[1, 1, 3, 5]
[1, 2, 2, 2, 3]
[1, 2, 2, 5]
[1, 3, 3, 3]
[2, 2, 2, 2, 2]
[2, 2, 3, 3]
[2, 3, 5]
[5, 5]
[10]

БЛОГ НА HUSL

Найти всевозможные комбинации монет

Ответы (2 шт):