입력 된 숫자가 주어진 배열의 조합인지 알려주는 알고리즘이 있습니까? 배열의 숫자는 n 번 사용할 수 있습니다. 예 :-주어진 배열 :-( 1, 5, 7 및 10) 입력 : -17 (yes since 10x1 + 7x1) 65 (yes since 10x6 + 5x1) .. 여기서 10은 6 번 사용됩니다. 출력 : -2 7
배열의 숫자를 여러 번 사용할 수 있다면 쉬운 알고리즘이 있지만 (최고는 아닙니다) 알고리즘을 설명하겠습니다.
주어진 숫자 M에 대해 먼저 배열에서 가장 큰 숫자를 가능한 한 많이 사용합니다. 경우 k가장 큰 숫자가, 다음 찾을 n그러한 k*n <= M와 k*(n+1) > M. 그런 사이의 갭을 채우기 위해 배열에서 두 번째로 큰 수를 사용 k*n하고 M등등.
예 : 배열이 [1, 5, 7, 10]and M=138인 경우 10(배열에서 가장 큰 숫자)를 가능한 한 많이 사용하여 M계속하지 않고 최대한 가깝게 도달하십시오 . 이 경우에는 13 배 때문이다 10*13 = 130 < M = 138와 10*14 > 140 > 138 = M. 그런 다음 두 번째로 큰 숫자 7을 사용하여 누락 된 부분 인 8 ( 138-130) 을 채 웁니다 . 그런 다음 분명히 5 (작동하지 않음)를 사용하고 마지막으로 1을 사용하십시오. 그러면 1 + 7 + 10 * 13 = 138이됩니다.
위의 알고리즘은 작동이 보장되지 않습니다. 배열이 [5, 7, 10]이면 알고리즘은 솔루션이 존재하더라도 솔루션을 찾지 않습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다