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*500*exchange_rate_500_note + i*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)] print("Optimal exchanged value: ", minx) print("How much I need to add: ", minx-original_value) print("Total 500 note: ", note) print("Total 100 note: ", note)