查找整数的线性组合

Question

我试过，但我找不到类似的问题。如果有重复的问题，请给我链接。

我看到有人在论坛上问了一个有趣的算法问题。问题是你有多少种方法可以将106分成10,20,50,1,2和5的线性组合？例如，106 = 10 * 6 + 1 * 6,106 = 50 * 2 + 2 * 1 + 1 * 4。

我使用python来解决这个问题，但它非常慢。而且我还概括了我的功能，因此它不仅可以应用于106而且可以应用于其他数字。

有没有办法让我的算法更快？获得160种方法需要几分钟，这是所有解决方案中的一小部分，我没有耐心等待更多结果，因为递归会导致一个解决方案需要花费越来越多的时间。

def main(total,*args):
    def recursion(Sum,method):          
        for arg in args:
            if Sum<arg:
                continue
            method[arg]+=1
            if Sum>arg:
                recursion(Sum-arg,method)
            else:
                methods.append(method.copy())
            method[arg]-=1
    methods=[]
    recursion(total,{ arg:0 for arg in args})
    return len(methods)

main(106,10,20,50,1,2,5)

Answer 1

这类似于硬币变化问题。您可以参考以下链接获取解决方案的各种方法：coin change problem gfg