Subset sum problem 및 Sum-subset with a fixed subset size 다음은 부분 집합 합계 문제를 해결하기위한 일반적인 알고리즘에 대해 궁금합니다. 여기서는 정확히 k 개의 정수 k < = n을 사용해야합니다.정확히 k 개의 정수에 대한 부분 합계?
Evgeny Kluev는 k = 4에서 최적으로 사용하고 k- 4에서 무차별 접근법을 사용하고 나머지는 최적이라고 설명했습니다. 누구나 최적의 k = 4 알 고와 결합 된 무차별 적 접근에 의해 그가 의미하는 것을 밝힐 수 있습니까?
누군가가 더 나은 일반 솔루션을 알고 있을까요?
원래의 동적 프로그래밍 알고리즘이 약간 확장되어 있습니다. 부분 합계를 기억하는 것 외에도 합계를 얻는 데 사용 된 int 수를 기억해야합니다. 대상 합 가정 원래 알고리즘
가M이고
n 정수 존재하면
A[i,m] 처음부터 (임의의 수)를 선택하여 달성 할 수에만 true 합
m되는 부울
n X
M 배열
A을 채우기
i+1 ints (0부터 인덱싱 가정).
당신은 유사한 특성을 갖는 삼차원 배열 nM X X k로 확장 할 수있다 - A[i,m,l] 먼저 i+1의 int l에서 정확히 선택하여 달성 할 수에만 true, m 합이다. 의 int 가정
배열 j[0..n-1]에 있습니다
재귀 관계는 매우 유사하다 - A[0,j[0],1]에 해당하는 분야 (당신이 1 개 INT (대만족)와 합 j[0]을 받고, j[0] 선택), A[0,*,*] 다른 필드는 거짓 및 A[i,*,*]에서 A[i+1,*,*]에서 파생 필드는 원래의 알고리즘과 유사합니다 A[i,m,l]에 해당하는 경우 ((당신이 먼저 i의 int에서 m를 선택할 수 있습니다 다음 분명히 먼저 i+1의 int에서 m를 선택할 수있는 경우) 또는 A[i, m - j[i+1], l-1]에 해당하는 경우 A[i+1,m,l]이 참 만약 너라면 j[i+1]을 선택한 다음 합계를 j[i+1] 및 int 수를 1 씩 늘립니다.
k이 작은 경우 분명히 위의 모든 부분을 건너 뛰고 k ints의 모든 조합을 반복하고 합계를 확인하는 것이 좋습니다. k<=4은 실제로 합리적인 문턱처럼 보입니다.
위와 어떻게 비교되는지 궁금합니다. http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset -size/8926458 # comment12539828_8926458 – Bober02
알고리즘을 여러 번 적용해야합니까? 또는 한 세트의 숫자에 대해서만? 그것은 단지 하나의 숫자 집합이라면 수동으로 숫자를 가지고 놀아서 패턴, 희소성 등을 알아내는 것이 좋습니다 –
글쎄, 한 번만 집어 야하지만 여전히 부 자연스러운 것은 아닙니다. 배열에서 정확히 k 개의 요소를 가져와야하므로 내 질문이 – Bober02