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:
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