Подбор платежей под сумму

pp = {200: 457, 50: 152}  # номинал: количество
summa = 540
...
res = {200:2, 50:3}  # либо [200, 200, 50, 50, 50]
# при pp = {200: 1, 50: 15}, res = {200:1, 50:7} либо [200, 50, 50, 50, 50, 50 ,50, 50]

baks = 1113.1
nominals = [2,1,5,10,50]
 
nominals.sort()
nominals.reverse()
 
print baks, '$ =>'
 
for k in nominals:
    d = baks//k
    baks = baks -d*k
    print k,'$ :',int(d)
 
print 'nerazmeneno:', baks
# отсюда      http://python.su/forum/topic/9749/?page=1#post-62796

a = 1113.1
d = dict.fromkeys([50, 10, 5], 0)
 
def get_nearest_value(iterable, value):
    return min(iterable, key=lambda x: abs(x - value))
 
d[50] = _50 = a/50
a = a%50
d[10] = _10 = a/10
a = a%10
d[5] = _5 = a/5
a = a%5
 
_key = get_nearest_value(d.keys(), a)
d[_key] += 1
 
for k in d.keys():
    print('%s - %d' % (k, d[k]))

a = 1113.1
d = dict.fromkeys([50, 10, 5], 0)
 
def get_nearest_value(iterable, value):
    return min(iterable, key=lambda x: abs(x - value))
 
for i in d.keys():
    d[i] = _i = a/i
    a = a%i
 
_key = get_nearest_value(d.keys(), a)
d[_key] += 1
 
for k in d.keys():
    print('%s - %d' % (k, d[k]))

a = 1113.1
d = {200: 1, 100: 15, 50: 75}        # 200 - 1
...
# выводит
# 200 - 5
# 100 - 1
# 50 - 1

a = 1113.1 # сумма к оплате
d = dict.fromkeys([50, 10, 5], 0) # номиналы
 
def get_nearest_value(iterable, value): # поиск ближайшего по значению элемента
    return min(iterable, key=lambda x: abs(x - value))
 
for i in d.keys():# в цикле считается колво по номиналам
    d[i] = _i = a/i
    a = a%i
 
_key = get_nearest_value(d.keys(), a)
d[_key] += 1
 
for k in d.keys():# вывод колва в цикле
    print('%s - %d' % (k, d[k]))

a = 1733.1
d = dict.fromkeys([50, 10, 5], 0)
have = {50: 50, 10: 10, 5: 5}
 
def get_nearest_value(iterable, value):
    return min(iterable, key=lambda x: abs(x - value))
 
for i in d.keys():
    d[i] = _i = a/i
    a = a%i
 
_key = get_nearest_value(d.keys(), a)
d[_key] += 1
 
for k in d.keys():
    print(f'{k} - {int(d[k])}, осталось банкнот - {int(have[k] - d[k] + 1)}')

# подбор платежей под сумму с минимальной переплатой
# по мотивам vba-скрипта отсюда http://www.excelworld.ru/forum/3-5196-3 (автор - МСН)
from math import ceil as toUP
 
 
def round_up(sum_value, base_value):
    return toUP(sum_value / base_value) * base_value
 
 
def count(n, s_max, s_min, dp_arr, array):
    for i in range(1, n):
        if 0 < array[i][0] <= s_max:
            for j in range((s_max - array[i][0]), -1, -1):
                if dp_arr[j]:
                    jj = j
                    for ii in range(1, array[i][1] + 1):
                        jj = jj + array[i][0]
                        if jj > s_max:
                            break
                        if dp_arr[jj] == 0:
                            dp_arr[jj] = i
                            if jj >= s_min:
                                k = jj
                                return k, dp_arr
 
 
def subset_sum(input_arr, sum_value):
    input_arr.sort(reverse=True)
    min_nominal = input_arr[-1][0]
    sum_value = round_up(sum_value, min_nominal)
 
    array = [[int((i * 100) / (min_nominal * 100)), j] for i, j in
             input_arr]
    mult = 100 / (100 * min_nominal)
    s_min = s_max = round(sum_value * mult)
    array.insert(0, 0)
    n = len(array)
    dp_arr = [0] * (s_max + 1)
    if s_min > s_max or s_min == 0:
        s_min = s_max
    dp_arr[0] = -1
    k, counter = count(n=n, s_max=s_max, s_min=s_min, dp_arr=dp_arr, array=array)
    if k < s_min:
        for k in range(s_min - 1, 0, -1):
            if dp_arr[k] > 0:
                break
    subset_index_arr = [0] * n
    while k > 0:
        subset_index_arr[dp_arr[k]] = subset_index_arr[dp_arr[k]] + 1
        k = k - array[dp_arr[k]][0]
    print(subset_index_arr)
    subset_index_arr = subset_index_arr[1:]
    return {input_arr[i][0]: subset_index_arr[i] for i in range(len(input_arr))}
 
 
def main_line():
    sum_value = 490
    input_arr = [[50, 48], [200, 1], [100, 3]]
 
    result_dic = subset_sum(input_arr, sum_value)
    print(sum_value, ' - ', result_dic)
 
 
if __name__ == '__main__':
    main_line()