알고리즘 질문 ​​: 가장 잘 맞는 하위 집합

Question

나는 거래와 일치하는 프로그램을 작성 중입니다. 아래는 제가 현재 직면하고있는 문제에 대한 설명입니다. 알고리즘에 대한 도움이 필요합니다.

비슷한 속성 (거래일, 계정, 기호)을 가진 두 세트의 거래 A와 B가있는 경우, A 내의 거래 a와 B 내의 sum (a)가 sum (b) . 여기서 sum()은 해당 하위 집합에 대한 특정 속성 (순 비용)의 합계입니다. 가장 가까운 일치를 필요로하는 이유는 완벽한 일치 (이상적인 경우)를 얻지 못하면 다음으로 가장 가까운 것을 원하기 때문입니다. 주 : sum (a)는 sum (b)보다 크거나 작을 수 있습니다.

분명히 A와 B의 모든 조합을 생성하고 비교하는 무차별 대입 방식을 사용하지 않고이 작업을 수행하려고합니다.

나는 이것이 동적 인 프로그래밍 방법으로는 가능하다고 느낀다. 그러나 구체적인 것을 내놓을 수 없다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

이 문제는 NP 하드입니다.

증명은 NP-hard로 알려진 부분 집합 합계에서 감소한 것입니다. 합계 요소 집합 S와 일부 목표 번호 k가 주어진 부분 집합 합계의 모든 인스턴스가 주어지면 A를 집합 S로하고 B를 단일 집합 {k}으로 놓음으로써 문제의 인스턴스를 만들 수 있습니다. . 우리가 당신의 문제를 풀고 가장 가까운 일치가 정확하게 k를 합계하지 않는다는 것을 알게되면, S의 서브 세트를 합하여 k를 얻는 방법이 없다는 것을 알게됩니다. 그렇지 않으면, S에서 k까지의 원소를 합산하는 방법이 있다면, 일치는 k와 완벽하게 같을 것이고, 우리는 어떤 부분 집합이 목표에 합쳐지는 것을 안다.

이 문제는 NP 하드이기 때문에 다항식 시간 또는 무차별 방도보다 훨씬 나은 솔루션을 기대해서는 안됩니다. 좋은 결과를 얻으려면 문제를 좀더 풀어야 할 필요가 있다고 생각합니다.

Answer 2

아쉽게도 스테로이드는 subset-sum입니다. 문제 크기 (A와 B의 요소 수)에 대한 아이디어가 있으면 좋을 것입니다. 문제는 확실히 NP 하드 일 수 있으므로 아래와 같은 정확한 솔루션을 사용하지 못할 수도 있습니다.

하나의 간단한 DP 솔루션은 가능한 모든 합계 값에 대해 A와 B의 하위 집합 합계를 개별적으로 해결하는 것입니다. 따라서 각 세트에 0과 50 사이의 요소가 10 개까지있는 경우 A와 B 모두에 대해 DP를 사용하여 0과 500 사이의 X에 대해 "X에 합계 된 하위 집합이 있습니까?"라는 질문에 답합니다. 두 세트를 통해 어떤 공통 값을 가지는지 보거나 A의 가능한 합계에서 B의 가능한 합계까지의 최소 거리를 찾으십시오.

(참고 : '효율적인'이 아닌 '단순한'이라고 말했습니다. 그러나 NP 경도 등으로 인해 big-O 조건에서 이보다 훨씬 더 빠른 해결책은 없습니다.)

Answer 3

그래서 무차별 대입 알고리즘의 경우 A와 B의 수퍼 세트를 만들고 그 (것)들을 합계하고, 합계의 절대를 건설하고 최소를 찾아 내십시오?

sa = superset (A) //() (a) (e) (i) (a, e), (a, i) (e, i) (a, e, i) 
sb = superset (B) 

sas = supersetAsums // 0, a, e, i, a+e, a+i, e+i, a+e+i 
sbs = supersetAsums 

ssas = sorted (sas) 
ssbs = sorted (sbs) 

이제 두 목록을 반복 할 경우 SSAS (I) < ssbs (J)이 증가 J, 내가 다른 증가하고 복근 (차이)가 현재의 분 (ABS (차이보다 작은 여부를보고)).

여기서 문제는 N. :