숫자 목록이 N입니다. 각 목록에서 k 숫자를 선택하고이 방법으로 형성 될 수있는 가장 큰 세트 (중복 없음)를 반환하십시오. 같은 크기의 세트가 여러 개 있으면 그 중 하나를 반환 할 수 있습니다. 예를 들어중복없이 각 카테고리에서 k 개의 번호를 선택하고 선택 항목을 최대화하십시오.
는 N = 3 인 경우, k는,
l1: [1, 2, 3]
l2: [2, 7]
l3: [3]
그때 최적의 결과 [1, 3, 2, 7] = 2. l1에서 [1, 3]을 선택하고 l2에서 [2, 7]을 선택하고 l3에서 [3]을 선택하십시오. (거기에 다른 선택하지만 결과 집합의 원소의 개수는 이것보다, 그래서하지만이 사람은 최고의 선택입니다.)
일부 표시등을 켜십시오. 미리 감사드립니다!
이 문제는 최대 2 부분 일치로 해결할 수 있습니다. 그것은 고전적인 알고리즘이며 그 설명은 인터넷에서 쉽게 찾을 수 있으므로 여기에 포함시키지 않겠습니다.
이 알고리즘은 다항식 시간이므로 NP는 문제가되지 않습니다.
두 부분으로 구성된 매칭 문제는 두 부분으로 된 그래프에서 각 꼭지점이 최대 하나의 선택된 가장자리에 인접하도록 가장자리 세트를 선택하고 가능한 세트 중에서 최대 카디널리티가있는 세트를 찾습니다.
두 부분으로 된 그래프를 만들어 보겠습니다. 왼쪽 부분에는 입력에 나타나는 모든 고유 번호에 대한 정점이 있습니다. 오른쪽 부분에는 각 목록 당 k 정점이 있습니다. 이제 "숫자"버텍스는 모든 "목록"버텍스와 연결되어 목록에 숫자가 포함됩니다.
이 그래프에서 최대 일치의 카디널리티는 문제에 대한 해답입니다. 하나의 목록에서 k 개 이상을 취하지 않고 최대한 많은 수의 고유 한 숫자를 취했습니다. 여기에 대답을 늘릴 수 없기 때문에 목록에서 k 개의 항목을 가져갈 수 있습니다. 필요하다면 여분의 (쓸데없는) 아이템을 가져갈 수 있습니다.
최대 흐름에 대해 알고 있다면 k - 용량 에지가 싱크되도록 각 목록마다 하나의 정점 만 추가하는 것을 고려할 수 있습니다. 이것은 본질적으로 동일하지만 더 빠른 점근 시간을 산출합니다.
아마도이 문제를 잘 이해하지 못 하겠지만 모든 목록의 모든 요소를 세트에 추가하고 선형 시간으로 최대한의 결과를 얻을 수있는 것 같습니다. (그러면 무작위로 결과 세트에서'k' 번호를 고를 수 있습니다.) – alfasin
@alfasin 그러면'k' 숫자가 선택됩니다. l1 = [1,2], l2 = [3,4,5,6,7], k = 2이면 [1,2,3,4,5,6,7]에서 무작위로 4를 선택하면 [4,5,6,7]은 l1에 1,2를 포함하지 않는다. 따라서이 경우 최종 결과는 l1의 [1, 2]를 포함해야합니다. 그것은 의미가 있습니까? – zsong
그러나 당신이'최대'해결책을 찾고 있다면 당신은 무작위로 아무 것도 할 수 없습니다 ... – alfasin