https://v2ex.com/t/895464 发票凑整

result.txt

sum(a): 10656
sum(b): 10656
a = 1776 , len(b) = 83, sum(b) = 10656
         588
         504
         280
         224
         180
a = 2667 , len(b) = 78, sum(b) = 8880
         364
         336
         280
         252
         224
         224
         196
         196
         140
         140
         120
         115
         40
         40
a = 6213 , len(b) = 64, sum(b) = 6213
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         28
         40
         40
         40
         56
         56
         56
         56
         56
         56
         56
         56
         56
         56
         56
         56
         84
         84
         84
         84
         84
         84
         84
         84
         84
         112
         112
         112
         112
         112
         120
         140
         168
         345
         2492

v2ex_895464.py

from functools import lru_cache

a = [17.76,62.13,26.67] #62.13,17.76,]
b = [24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

a = [round(i*100) for i in a]
b = [round(i*100) for i in b]

a.sort()
b.sort()

print("sum(a):", sum(a))
print("sum(b):", sum(b))

def main(a):
    for aa in a:
        print(f"a = { aa } , len(b) = { len(b) }, sum(b) = { sum(b) }")
        # print(b)
        findAinB(aa, 0)
 
@lru_cache(maxsize=10240)
def findAinB(a1, ib):
    # print(a1, ib)
    if ib >= len(b):
        return False

    if a1 == sum(b[ib:]):
        for i in b[ib:]:
            print('\t', i)
            b.remove(i)
        return True

    b1 = b[ib]
    if a1 < b1:
        return False
    elif a1 == b1:
        print('\t', b1)
        b.pop(ib)
        return True

    if findAinB(a1, ib+1):
        return True
    elif findAinB(a1-b1, ib+1):
        print('\t', b1)
        b.pop(ib)
        return True
 
    return False


main(a)

v2ex_895464_v2.py

#!/usr/bin/env python3
# coding: utf-8
# vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4:

import itertools as it

a = [52.7,8.96]
b = [21.44,6.72,5.44,5.12,4.48,3.20,2.24,1.92,1.92,1.92,1.28,1.28,1.00,0.96,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32]

a = [62.13,26.67,17.76]
b = [24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

a = [round(i*100) for i in a]
b = [round(i*100) for i in b]


def comb(n, lst):
    new_lst = [i for i in lst if i <= n]
    if sum(new_lst) == n:
        return new_lst

    for i in range(1, len(new_lst)+1):
        # print(f'C({len(new_lst)}, {i})')
        for j in it.combinations(new_lst, i):
            if sum(j) == n:
                return j

def resolve(n, lst):
    new_lst = [i for i in lst if i <= n]
    if sum(new_lst) == n:
        return new_lst

    uniq_elem = set(new_lst)
    # count for each element
    max_repeat = 1
    for k in uniq_elem:
        max_repeat = max(max_repeat, new_lst.count(k))

    # 用最小重复次数求解，如果不行，元素重复次数加1，再求解
    min_lst = []
    for i in range(1, max_repeat+1):
        for k in uniq_elem:
            if k in new_lst:
                new_lst.remove(k)
                min_lst.append(k)
        if sum(min_lst) == n:
            return min_lst
        print('round:', i, 'len(lst):', len(min_lst))

        # 减少排列组合次数
        for i in sorted(uniq_elem, reverse=True):
            n0 = min_lst[0]
            n1 = n - n0
            ans = comb(n1, min_lst[1:])
            if ans:
                return [n0] + list(ans)

a.sort()
# b.sort(reverse=True)
assert sum(a) == sum(b)

for i in a:
    ans = resolve(i, b)
    if ans:
        print(f'{i} = {" + ".join(map(str, ans))}')
        [ b.remove(i) for i in ans ]