디자인, n 개의 정수의 집합 S 다른 정수 X 주어진 에 (N> K> 2) 요소 K가 존재하는지 여부를 결정하는 알고리즘 S는 정확히 x입니다. 알고리즘의 실행 시간을 알려주십시오.합계
나는 인터뷰를 준비하고 있으며이 알고리즘을 발견했습니다. 문제점에 k가 지정되어있는 문제를 해결했습니다. 2 또는 3처럼. 그러나 나는 존재할 수도있는 어떤 k에 대해서도 풀 수있는 답을 찾을 수 없다. 동적 프로그래밍을 사용하여 문제를 해결하려고했지만 결과를 얻지 못했습니다. 누구든지이 일을 도와 줄 수 있어요.
int 어레이 cnt을 x 크기로 만든 다음 도달 가능한 지점을 표시 할 수 있습니다. cnt의 모든 요소는 0으로 설정된 요소 0을 제외하고는 처음에 -1으로 설정됩니다.
반복하여 각 요소의 Ssi 대해 동일한 프로세스 (이 배열의 범위 내 인 경우) 비 - 네거티브 위치 icnt에서의 각 요소에 대해, 소자 cnt[i+si]를 확인한다. 이 경우 cnt[si+i] = max(cnt[i]+1, cnt[si+i])으로 설정하십시오.
S의 모든 요소를 확인한 후에는 cnt[x]을 확인하십시오. 두 개 이상으로 설정된 경우 x까지 합치는 S에 두 개 이상의 요소가 조합되어 있습니다.
이 알고리즘은 시간 O(x*|S|)
을 실행하는, 의사 다항식 집합 S의 정수가 긍정적, 또는 그들은 또한 음수가 될 수 있습니까? – user502144
이 문서가 문제를 해결합니까? http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ – user502144