2
다중/다목적 subset-sum problem에 대한 빠른 솔루션을 찾고 있습니다.다차원 부분 집합 합을위한 의사 다항식 또는 빠른 솔루션
덧붙여서 (IMO를 계산하기 쉽도록 만드는) 추가 제한으로 합계에 포함 된 모든 값이 양수이고 모두 알려진 한계 값에 바인딩되어 있다고 가정 할 수 있습니다.
나는 O-NK pseudopolynomial 솔루션이 하나의 목적을 가진 부분 집합 합계 문제에 대해 알고있다. 나는 wikipedia 기반의 솔루션을 구현했으며 this 스택 교환 응답을 구현했다.
다른 방식으로이 문제를 설명하면 한계가 알려진 두 세트의 양수가 있습니다. 첫 번째 집합의 각 값 A에 대해 A까지 합계 한 두 번째 집합의 값의 조합이 있습니다. 첫 번째 집합의 모든 값은 두 번째 집합에 연결된 값의 상응하는 충돌하지 않는 조합을가집니다. 두 번째 집합의 어떤 요소가 첫 번째 집합의 각 값과 관련되는지를 알려주는 빠른 방법이 있습니까?
"충돌하지 않는다"는 것이 정확히 무엇을 의미합니까? 두 번째 집합의 각 값이 A의 값 중 하나만 만드는 데 사용된다는 것을 의미합니까? 아니면 A의 값에 대한 각 솔루션이 고유하다는 뜻입니까 (즉, 두 번째 집합의 하위 집합 중 하나만 해당 값을 생성합니다) 또는 다른 것을 의미할까요? –
@ JerryCoffin에서 두 번째 집합의 각 값은 A의 값 중 하나만을 만드는 데 사용됩니다. – viniciuscb
이와 같은 문제는 첫 번째 집합의 값까지 합계 할 수있는 여러 가지 조합이 두 번째 집합에있을 수 있습니다. 문제는 첫 번째 집합의 각 값에 대해 하나의 조합을 찾아야하고 두 번째 집합에서 모든 발견 된 조합이 독점적 인 값을 사용해야한다는 것입니다. 이는 충돌하지 않는다고 말하는 것입니다. – viniciuscb