두 배열에있는 요소의 동일한 합계

Question

길이가 같은 두 개의 정수 배열 v1 및 v2이 있습니다. 나는 v1의 요소 중 가장 큰 부분 집합을 찾는데 그 합은 v2에있는 해당 요소의 것과 동일합니다. 이것이 내가 찾고 있어요 하위 집합이 될 것이다, 그래서 예를 들어, 두 배열에

v1 = [1 2 3 1] 
v2 = [2 3 1 2] 

2, 3, 4 요소의 합이다 6을 할 수 있습니다.

계산 방법이 있습니까?

미리 감사드립니다. 체사레

Answer 1

델타를 계산하면 문제가 subset sum problem으로 줄어 듭니다. 다시 말해, 각 요소가 두 입력 배열의 해당 요소 사이의 차이 인 세 번째 배열을 만듭니다. 입력 어레이 v1 및 v2 주어진 예

, 차이를 포함하도록 구성 배열을 작성 v3 :

 0 1 2 3 <-- index into the array 
v1 = [ 1 2 3 1] 
v2 = [ 2 3 1 2] 
v3 = [-1 -1 2 -1] 

그럼 0에 추가 v3 어떤 서브 세트는 용액이다. 이 예에서 솔루션은 {0,1,2}, {0,2,3} 및 {1,2,3}과 같은 인덱스 집합으로 표시됩니다.