정수의 선형 조합 찾기

Question

시도했지만 비슷한 질문을 찾을 수 없었습니다. 중복되는 질문이 있으면 저에게 링크를주십시오.

누군가 포럼에서 흥미로운 알고리즘 문제를 묻는 것을 봤습니다. 문제는 106을 10, 20, 50, 1, 2 및 5의 선형 결합으로 몇 가지 방법으로 나눌 수 있는지 묻습니다. 예를 들어, 106 = 10 * 6 + 1 * 6, 106 = 50 * 2 + 2 * 1 + 1 * 4.

이 문제를 해결하기 위해 파이썬을 사용했지만 속도가 느립니다. 그리고 저는 제 기능을 일반화하여 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