임계 값 이상의 최소 부분 집합 합을 찾기위한 선형 알고리즘

나는 각각 (상대적으로 작은) 상수 C로 경계가 정해진 N 개의 양의 정수 집합을 가지고 있습니다.이 작은 수의 부분 집합을 (또는 값이 K와 같습니다.임계 값 이상의 최소 부분 집합 합을 찾기위한 선형 알고리즘

관련된 숫자는 크게는 아니지만 (< 100) 최악의 경우에도 성능이 좋아야합니다. 필자는 Pisinger의 동적 프로그래밍 알고리즘을 작업에 적용 할 수 있을지도 모른다고 생각했습니다. 그것은 오 (노스 캐롤라이나) 시간에 실행되며, 나는 양수의 한정된 요구 사항을 충족하는 일이.

[편집] : 숫자는 정렬되지 않으며 중복 될 수 있습니다.

그러나 알고리즘 자체를 잘 이해하지 못합니다. 사실, 그것이 여전히 기반으로 가정은 확실하지 않다 ...

- 내 필요에 맞게이 알고리즘을 적용 할 수 있습니까?

또는 거기에 비슷한 선형 알고리즘을 사용할 수 있습니까?

의사 코드 또는 자세한 설명을 제공 할 사람이 있습니까?

감사합니다. NP 집 - 합계 코드

링크는 내가 조사되었다 Fast solution to Subset sum algorithm by Pisinger

(사과를이 저조한/포맷/등 난 ... 아직 StackOverflow의 새로운이야 말로 경우.)

출처

2013-06-18 Athena

은 이것이 배낭 문제의 변형이 아닙니까? – phoeagon

예. 특히, Subset-Sum (자체는 배낭의 특별한 경우)의 변형입니다. – Athena

나중에 참조 할 수 있도록 중복이있는 경우 "집합"이라는 용어를 사용하지 마십시오. "collection"은 더 나은 용어입니다. –

Pisinger 알고리즘을 사용하면 배낭의 용량보다 작거나 같은 최대 합계를 얻을 수 있습니다. 문제를 해결하려면 Pisinger를 사용하여 이 아닌이 무엇인지 파악하십시오. 공식적으로 아이템을 w_1, ..., w_n, 최소값을 K라고하면 다음과 같습니다. w_1, ..., w_n 및 w_1 + ... + w_n-K를 Pisinger에게주고 Pisinger가하지 않는 모든 아이템을 가져옵니다.

출처

2013-06-19 00:25:55

당신이 말한 것처럼 역 연산을 고려해 보았지만, 선형 적이 지 않은 O (n (n-k)) = O (n^2)입니다. – Athena

@Athena Pisinger의 실행 시간은 O (항목 수 * 최대 항목)이며 배낭 크기 나 최적의 솔루션 저장 항목 수에 좌우되지 않습니다. –

아, 맞습니다! (내 상수가 섞여있어.) 내 목적을 위해 작동합니다. 많은 감사합니다! – Athena

잘 하나 해결 방법은 다음과 같습니다.

T = {0} 

for x in V 
    for t in T 
     T.insert(x+t) 

for i in K to max(T) 
    if (T.contains(i)) 
     return i 

fail

이렇게하면 하위 집합의 크기를 알 수 있지만 구성원을 출력 할 수 있습니다.

T의 최대 크기는 O (N) (C 바인딩으로 인해)이므로 실행 시간은 O (N^2)이고 공간은 O (N)입니다. 길이가 NC 인 비트 배열을 T의 후원 스토어로 사용할 수 있습니다.

출처

2013-06-18 03:39:45

O (N^2) 알고리즘이 선형으로 간주하지 않는다고 생각합니다. –

오, 제목을 알아 채지 못했고, 우리는 단지 다항식 시간 동안 노력하고 있다고 생각했습니다. –

"선형"이라고하는 질문을 명확히 할 것입니다. 어쨌든 고마워. – Athena

임계 값 이상의 최소 부분 집합 합을 찾기위한 선형 알고리즘

답변

관련 문제