How to distribute value between fixed amount of notes

I have 512 notes between the values ​​of 200, 100, 50, 20, 10, 5 and 2. The sum of these notes ​​is exactly 1397. How much of each note do I have with none of them being 0?

Answer:

• 200: 1 note
• 100: 1 note
• 50: 1 note
• 20: 1 note
• 10: 1 note
• 5: 1 note
• 2: 506 notes

I know there are several possibilities, how I can write a algorithm who return at least one solution for any number of notes and any sum of values? I need to make an code in Python. Thanks!

EDIT: Thanks to Kelly Bundy in the comments, it turns out I'm trying to find an impossible solution with my bad example. So, with the comment edited, I arrived at this code:

def find_note_combinations():
    for x1 in range(1, 513):
        for x2 in range(1, 513):
            for x3 in range(1, 513):
                for x4 in range(1, 513):
                    for x5 in range(1, 513):
                        for x6 in range(1, 513):
                            for x7 in range(1, 513):
                                if x1 + x2 + x3 + x4 + x5 + x6 + x7 == 512 and 200 * x1 + 100 * x2 + 50 * x3 + 20 * x4 + 10 * x5 + 5 * x6 + 2 * x7 == 1397:
                                    return x1, x2, x3, x4, x5, x6, x7

x1, x2, x3, x4, x5, x6, x7 = find_note_combinations()
print("Number of 200 notes:", x1)
print("Number of 100 notes:", x2)
print("Number of 50 notes:", x3)
print("Number of 20 notes:", x4)
print("Number of 10 notes:", x5)
print("Number of 5 notes:", x6)
print("Number of 2 notes:", x7)

But it's ugly and inefficient, help?

You can use a recursion for the task (I recommend to sort the notes array from lower bill to bigger one):

# notes dict (we must have 1 of each at minimum)
notes = [
    [2, 1],
    [5, 1],
    [10, 1],
    [20, 1],
    [50, 1],
    [100, 1],
    [200, 1],
]

def find_solution(target, amount, notes):
    s = sum(n * a for n, a in notes)

    if amount == 0 and s == target:
        return True

    if s > target or amount < 0:
        return False

    for i in range(len(notes)):
        notes[i][1] += 1
        if find_solution(target, amount - 1, notes):
            return True
        notes[i][1] -= 1

    return False

if find_solution(1397, 512 - len(notes), notes):
    print(notes)

Prints:

[[2, 506], [5, 1], [10, 1], [20, 1], [50, 1], [100, 1], [200, 1]]

EDIT: Adding some heurestics:

from itertools import product

notes = [
    [2, 1],
    [5, 1],
    [10, 1],
    [20, 1],
    [50, 1],
    [100, 1],
    [200, 1],
]

def find_solution(target, amount, notes):
    global steps
    steps += 1
    if steps > 1_000_000:
        return False

    s = sum(n * a for n, a in notes)

    if amount == len(notes):
        if target - s not in amount_shorcut:
            return False
        else:
            for val in amount_shorcut[target - s]:
                for i in range(len(notes)):
                    if notes[i][0] == val:
                        notes[i][1] += 1
                        break
            return True

    if amount == 0 and s == target:
        return True

    if s >= target or amount <= 0:
        return False

    for i in range(len(notes)):
        notes[i][1] += 1
        if find_solution(target, amount - 1, notes):
            return True
        notes[i][1] -= 1

    return False

amount_shorcut = {}
for t in product([n for n, _ in notes], repeat=len(notes)):
    amount_shorcut[sum(t)] = t

AMOUNT = 12345
N = 87
notes = sorted(notes, key=lambda l: abs(l[0] - (AMOUNT / N)))

# step 1:
steps = 0
if find_solution(AMOUNT, N - len(notes), notes):
    print(notes)
else:
    # step 2 (swap first two bills):
    steps = 0
    notes[0], notes[1] = notes[1], notes[0]
    if find_solution(AMOUNT, N - len(notes), notes):
        print(notes)

print('Total amount of steps:', steps)

This prints:

[[200, 60], [100, 2], [50, 1], [20, 2], [10, 1], [5, 1], [2, 20]]
Total amount of steps: 60434