# Find the lowest difference in exchanged value

I was wondering if this type of problem can be modelled with Linear Programming or any other approach that much more efficient.

Let say I've 5500 in original currency. I want to convert to other currency with exchange rate of 1.12 and 1.135 for 500 and 100 notes respectively. The objective is the combination of these 2 notes must be equal or bigger than 5500. Since the value can be higher than 5500, I want to know how much I need to top up and want to get the minimal top up amount from the combination.

So far, I came up with a simple linear equation

$$1.12(500)x + 1.135(100)y >= 5500$$

I can solve this by iteratively substitute the combination of x and y in the equation and find the lowest difference between 5500 and result.

Here is the python code that demonstrate the approach.

import itertools
import math
import numpy as np

# 1.12(500)x + 1.135(100)y >= 5500
exchanged = []
comb = []
original_value = 5500
exchange_rate_500_note = 1.12
exchange_rate_100_note = 1.135

# generate possible combination of the two notes
list_500 = np.arange(math.ceil(original_value / exchange_rate_500_note / 500))
list_100 = np.arange(math.ceil(original_value / exchange_rate_100_note / 100))
for i in itertools.product(list_500,list_100):
sumx = i[0]*500*exchange_rate_500_note + i[1]*100*exchange_rate_100_note
if sumx - origin_value >= 0:
exchanged.append(sumx)
comb.append(i)

exchanged = np.array(exchanged)
minx = np.min(exchanged)
note = comb[np.where(exchanged == minx)[0][0]]
print("Optimal exchanged value: ", minx)
print("How much I need to add: ", minx-original_value)
print("Total 500 note: ", note[0])
print("Total 100 note: ", note[1])


• Why wouldn't you just change it all into the bills with the more favorable exchange rate? – saulspatz Nov 15 '19 at 3:37
• @saulspatz the objective is to get the minimum top up amount. If I simply assign 10 to x and 0 to y. I'll need to add additional 100. – Mahadir Ahmad Nov 15 '19 at 6:48