이 퍼즐 - 서브 세트 합계? 가디언 (영국 신문)의 오늘의 판에서

Question

이, 크리스 마스 랑카하여 43 페이지의 "Pyrgic 퍼즐"섹션에서 다음 퍼즐이 주어졌다 :

3 현명한 사람을 ...했다 Herrods 크리스마스 쇼핑을하십시오. Caspar는 금을, Melchior는 Frankincense를, Balthazar는 의 복사본을 매일 Myrrh으로 구입했습니다. 계산원은 이러한 모든 비용의 유로 수를 계산하여 3 개의 숫자를 더하지만 대신 계산했습니다. ... 결과의 경이는 65.52 유로였습니다. 3 개의 합계는 무엇입니까 [그가 세의 세 가지를 의미한다고 가정하니?]

내 해석이된다 , B및 C 등이 + B + C = ABC = 65.52 찾기 (정확하게) 여기서 , b 및 c은 소수점 두 자리 이하의 양수 십진수입니다. , b 및 c도 65.52 (약)보다 작아야합니다.

내 접근 방식은 따라서이다 : 나는 의 모든 후보 세트를 찾을하여야한다, B와 C + B + C = 6552과, Bc은 {1 ... 6550}의 정수입니다 (편의상 모든 피연산자에 100을 곱한 것). 그런 다음 모든 후보 집합에 대해 모든 피연산자를 100으로 나눈 다음 임의의 정밀도 산술을 곱하여 다른 조건을 충족시키는 것이 쉽습니다.

이것은 내가보기에 부분 집합 합계 문제의 인스턴스입니다. 그래서 하나의 솔루션 (a = 0.52, b = 2, c = 63)을 발견 한 더러운 (지수 적 시간) 알고리즘을 구현했습니다.

좋아, 하위 집합 합계 문제에 대한 더 나은 알고리즘이 있지만 평균 가디언 리더에게는 약간의 도달 범위를 얻지 못했다고 생각하지 않습니까? 40 페이지의 대답에

가 나열됩니다 : 이것은 시행 착오에 의해, 쉽게

. 추측 52p에 대한 매일 Myrrh. 그러나 0.52를 곱하면 대략 반으로 줄어들므로 한 합이 약 2가되어야합니다. 그래서 2 X 63 X 0.52를 시도하십시오. Et voilà. 이 답변이 유일한가요?

글쎄, 우리는 답이 유일하다는 것을 알고 있습니다 (2, 63 및 0.52의 다른 순열은 무시합니다).

내가 알고 싶은 것은 : 어떻게 "쉬울 수 있습니까?" 나는 부분 집합 총합 문제의 실례로서 퍼즐을 특성화하는 데 바로 맞습니까?솔루션을 단순화하기 위해 활용할 수있는 퍼즐의 특성을 간과 했습니까? 누구든지 유사한 "시행 착오"접근법을 채택 할 수 있었습니까? 만약 그렇다면 그들은 그것을 통해 나를 데려 갈 수 있습니까? Chris Maslanka는 단순히 NP 완전 문제로 어려움을 겪지 않았습니까?

Answer 1

없음, 그 때문에, 서브셋 합 문제 인스턴스가 아닌 : 순 철저한 검색 (지수 생략) 그것에 O(n^3) 용액 최악 올라서

서브 세트의 크기는 제한되어

1. 3
2. 여기에 숫자의 제품인 추가 데이터가 있습니다.
3. 실제로 집합이 주어지지 않았지만 모든 정수 집합은 부분 집합 sum의 하위 문제 일뿐 훨씬 쉬운 집합입니다.

여기서 중요한 점은 : NP-Hard 문제로 문제를 해결할 수 있다면 그것이 NP 하드 일뿐만 아니라 다른 방법으로도 유지된다는 의미는 아닙니다. 문제가 있고 NP-Hard 문제 (다항식)를 풀 수 있다면 문제는 NP-Hard입니다. polynomial reduction 이라고합니다.

---

접근이 용이하기 때문에 당신이 a의 값을 (모든 후보자를 반복하여) "추측"할 일은해야하고,이에서 당신이 b, c에 대한 해결 방안이 무엇인지 도출 할 수있는 모든 - (2 변수, 두 개의 방정식이 있습니다. 즉, 각각의 반복에서 -)이므로 솔루션은 선형 적이기 때문에 하위 지수 형이 아닙니다.

하위 선형 최적화를 얻기 위해 다양한 이진 검색을 사용하도록 최적화되었을 수도 있지만, 지금은 최적화를 생각할 수 없습니다.

---

(1) 참고 : 이것은 직관적 인 설명이 아닌 직관적 인 설명입니다.