합계가 특정 임계 값보다 작은 최소 합계 인 서브 세트

Question

양의 정수 집합이 주어지면 합계가 임계 값을 초과하는 최소 합계 인 해당 정수의 서브 세트를 원합니다.

Answer 1

문제점은 Subset Sum Problem의 변형이며 NP 완성입니다.

왜 문제를 해결할 수있는 알고리즘이 있고 합계가있는 대답이 있다고 가정 해 봅시다. 그렇다면 s - 1과 같은 정수의 하위 집합이 존재하지 않는다는 것이 입증되었습니다. 즉 하위 집합 합계 문제에 대한 해답을 얻었습니다.

성능에 문제가 없다면 가능한 모든 세트를 열거 할 수 있습니다. 성능이 문제라면 위키 백과 페이지에서 동적 프로그래밍을 사용하는 등 알고리즘의 종류를 최적화하는 방법에 대한 아이디어를 찾아 볼 수 있습니다. 해당 페이지의 알고리즘은 사실 서브 세트 합계 문제만큼 효율적으로 문제를 해결해야합니다.

Answer 2

"작은 액수"물론 여기에 설명 된 클래식 "최대 금액"문제있다 : http://wordaligned.org/articles/the-maximum-subsequence-problem

이 그냥 작은 변화가 조건은 "이 임계 값을 초과"함께 - 그냥 여분이 경우 루프에서 문 .

Answer 3

나는 동일한 문제가있었습니다! 모든 N 개의 정수가 양수이고 상수 C로 한정되는 경우 O (NC)의 시간 및 공간 요구 사항이있는 솔루션이 있습니다.

Pisinger는 임계 값에서 최대 값을 찾기 위해 선형 시간 동적 프로그래밍 알고리즘을 발견했습니다. 이는 문제의 역함과 같습니다. 따라서 정수 총합에서 원하는 임계 값을 빼면 Pisinger의 알고리즘으로이 새 임계 값을 사용하여 원하는 세트에없는 모든 숫자를 찾을 수 있습니다.

정수의 크기에 따라 다르거 나 그렇지 않을 수도 있습니다.

Pisinger의 용지 : http://www.diku.dk/~pisinger/95-6.ps

코드 : Fast solution to Subset sum algorithm by Pisinger