부분집합 문제

서브셋 합계 문제(SSP)는 컴퓨터 과학의 결정 문제다. 그것의 가장 일반적인 공식에는 정수의 $S$ 멀티셋 $S$ $S$ 과 $표적섬$ T $T$ 이 있으며 $T$ 문제는 정수의 어떤 부분집합이 정확한 $T$ $T$ 에 합치되는지를 결정하는 것이다 $T$ ^[1] 문제는 NP-완전인 것으로 알려져 있다. 또한 제한된 변형도 NP-완전하다.^[1] 예를 들면 다음과 같다.

모든 입력이 양수인 변종.
The variant in which inputs may be positive or negative, and $T=0$ . For example, given the set $\{-7,-3,-2,9000,5,8\}$ , the answer is yes because the subset $\{-3,-2,5\}$ sums to zero.
모든 입력이 양수이고, 목표 합이 $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ 입력의 합계의 정확히 절반인 변형, 즉 T $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ = 1 $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ ( $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ + $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ ⋯ $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ + $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ $){\displaystyle T={\frac$ { $1}{$ 1}{ $1}}{1}:{n}}.$ SSP의 이 특별한 경우는 파티션 문제로 알려져 있다.

SSP는 또한 최적화 문제로 간주될 수 있다. 즉, 합계가 최대 T이고 그 대상이 되는 부분집합을 찾으면 T에 최대한 가깝게 된다. NP-hard이지만, 실제로도 합리적으로 신속하게 해결할 수 있는 알고리즘이 몇 가지 있다.

SSP는 배낭 문제와 복수 부분집합 문제의 특별한 경우다.

계산 경도

SSP의 런타임 복잡성은 다음 두 가지 매개변수에 따라 달라진다.

n

입력 정수 수

n(정수의 수)이 작은 고정수라면, 해법에 대한 철저한 검색이 실용적이다.

L

문제를 기술하는 데 필요한 이진수 위치 값의 수로 명시된 문제의 정밀도

L(이진 자리수)이 작은 고정수라면 이를 정확히 해결할 수 있는 동적 프로그래밍 알고리즘이 있다.

n과 L이 모두 클 때 SSP는 NP-hard이다. 가장 잘 알려진 알고리즘의 복잡성은 두 매개변수 n과 L 중 작은 부분에서 기하급수적이다. 다음과 같은 변형은 NP-hard로 알려져 있다.

모든 입력 정수는 양의 값이다(그리고 표적 합계 T는 입력의 일부임). 이것은 3SAT로부터의 직접적인 축소로 증명할 수 있다.^[2]
입력 정수는 양수 및 음수일 수 있으며, 대상 합 T = 0이다. 이것은 양의 정수를 가진 변종으로부터의 축소를 통해 증명될 수 있다. 이 변형은 SubsetSumPositive로, 현재 변형은 SubsetSumZero로 표시하십시오. SubsetSumPositive의 인스턴스(S, T)가 주어진 경우 값 -T로 단일 요소를 추가하여 SubsetSumZero의 인스턴스를 생성하십시오. SubsetSumPositive 인스턴스에 대한 해결책이 주어지면 -T를 추가하면 SubsetSumZero 인스턴스에 대한 해결책이 나온다. 반대로 SubsetSumZero 인스턴스에 대한 해결책이 주어지면 -T(S의 모든 정수가 양수이므로)를 포함해야 하므로, 0의 합을 얻으려면 S의 부분집합도 포함시켜야 하는데, 이는 SubsetSumPositive 인스턴스의 해결책이다.
입력 정수는 양수이고, T = 합(S)/2이다. 이는 일반적인 변종으로부터의 축소를 통해서도 증명될 수 있다. 파티션 문제를 참조하십시오.

지수 시간 알고리즘

시간 지수화 n에서 SSP를 해결하는 몇 가지 방법이 있다.^[3]

포함-제외

가장 순진한 알고리즘은 n개의 숫자의 모든 부분 집합을 순환하는 것이며, 그 모든 부분 집합에 대해 부분 집합이 올바른 숫자에 합치되는지 점검하는 것이다. 실행 시간은 순서 $O(2^{n}\cdot n)$ ( $O(2^{n}\cdot n)$ $){\displaystyle O (2^{$ n}\ $cdot$ n $)}$ 이며 $O(2^{n}\cdot n)$ $2^{n}$ ${\$ 하위 $2^{n}$ 집합이 있고, 각 하위 집합을 확인하려면 최대 n개의 요소를 합해야 한다.

알고리즘은 이진수 트리의 깊이 우선 검색을 통해 구현될 수 있다. 트리의 각 수준은 입력 번호에 해당하고, 왼쪽 분기는 세트에서 숫자를 제외하는 것에 해당하며, 오른쪽 분기는 숫자를 포함하는 것에 해당한다(이름 포함-제외). 필요한 메모리는 $O(n)$ ( $O(n)$ ) $O(n)$ 입니다 $O(n)$ 런타임은 몇 가지 경험적 접근법으로 개선할 수 있다.^[3]

입력 번호를 내림차순으로 처리하십시오.
주어진 노드에 포함된 정수가 지금까지 발견된 가장 좋은 부분 집합의 합을 초과하는 경우, 노드는 제거된다.
주어진 노드에 포함된 정수와 나머지 모든 정수가 지금까지 발견된 최상의 하위 집합의 합보다 작을 경우, 노드는 제거된다.

호로위츠와 사니

호로위츠와 Sani는^[4] 더 빠른 지수 시간 알고리즘을 발표했는데, 이 알고리즘은 시간 $2n$ / $O(2^{n/2}\cdot (n/2))$ ( $O(2^{n/2}\cdot (n/2))$ n / $O(2^{n/2}\cdot (n/2))$ ) {\ $displaystyle$ O $(2^{n/2}\cdot (n/2$ 에 실행되지만 훨씬 더 많은 공간이 필요하다 - $O(2^{n/2})$ O ( $O(2^{n/2})$ / $O(2^{n/2})$ ) ${\displaystystyle$ O ( $2^{n/2}).$ 알고리즘은 n 원소를 각각 $n/2$ n $n/2$ / $n/2$ $n/2$ 의 두 세트로 임의로 분할한다. 이 두 세트의 각각에 대해, 그것은 그것의 요소들의 $2^{n/2}$ 가능한 하위 $2^{n/2}$ $2^{n/2}$ $2^{n/2}$ $2^{n/2}$ ${\$ 개의 합계 목록을 저장한다. 그리고 나서 이 두 리스트는 각각 분류된다. 가장 빠른 비교 정렬 알고리즘을 사용하는 경우에도 이 단계의 병합에는 $O(2^{n/2}n)$ / $O(2^{n/2}n)$ ) ${\displaystyle O(2^{n/$ 2} $n)}$ 시간이 소요되지만, $k$ $k$ 요소의 $k$ 정렬된 합계 목록이 주어지면 $k+1$ ( $k+1$ + 1 ${\displaysty k+1$ 번째 요소의 도입으로 목록을 두 개의 정렬할 수 있다 $O(2^{n/2}n)$ , 그리고 이 두 개의 정렬된 목록은 $O(2^{k})$ O $O(2^{k})$ ( $O(2^{k})$ $O(2^{k})$ ) ${\displaystyle$ O $(2^{k}}}$ 에 병합될 수 있다 $O(2^{k})$ 따라서 각 목록은 시간 $O(2^{n/2})$ ( $O(2^{n/2})$ $O(2^{n/2})$ / $O(2^{n/2})$ ) ${\displaystyle$ O $(2^{n/2})$ 로 정렬된 형태로 생성될 수 있다 $O(2^{n/2})$ 두 개의 정렬된 목록을 볼 때 알고리즘은 첫 번째 어레이의 요소와 두 번째 어레이의 요소를 TI에서 확인할 수 있다.me $O(2^{n/2})$ ( $O(2^{n/2})$ / $O(2^{n/2})$ ) ${\displaystyle$ O( $2^{n/2$ 이를 위해 알고리즘은 첫 번째 어레이를 감소 순서로(2^{n/2}). 두 번째 어레이는 증가 순서로 통과한다(가장 큰 요소에서 시작). 첫 번째 배열의 현재 원소와 두 번째 배열의 현재 원소의 합이 T보다 클 때마다 알고리즘은 첫 번째 배열의 다음 원소로 이동한다. T보다 작으면 알고리즘이 두 번째 배열의 다음 요소로 이동한다. T에 합한 두 원소가 발견되면 정지한다.

슈뢰펠과 샤미르

슈로펠. 미국과 Shamir[5] 비슷한 런타임-오(/2⋅ 2n(n/4)){\displaystyle O(2^{}n/2 \cdot(n/4))}, 훨씬 적은 공간-오(2n/4){O(2^{n/4})\displaystyle}다. 오히려고 미리n/2 요소의 모든 하위 집합을 저장하는 발전보다, 그들은 partit가 필요한 알고리즘 호로위츠와 Sanhi에 기반을 두고 있었다.이온 요소는 각각 4 세트의 n/4 원소로 생성되며, $O(k^{2}\log(k))$ $O(k)$ 힙을 사용하여 n/2 원소 쌍의 하위 집합을 동적으로 생성하며, 이는 O $O(k^{2}\log(k))$ 2 $O(k^{2}\log(k))$ $O(k^{2}\log(k))$ ( $O(k^{2}\log(k))$ ) $O(k^{2}\log(k))$ {\ $display style$ O( $k^{$ 2}\ $log(k)})$ 및 $O(k^{2}\log(k))$ $O(k)$ O $O(k)$ {\ $displaysty style$ O( $k)}$ 에서 수행할 수 있기 때문이다.

공간 요구사항 때문에 HS 알고리즘은 최대 50개 정수에 실용적이고, SS 알고리즘은 최대 100개 정수에 실용적이다.^[3]

하그레이브-그레이엄과 쥬스

Howgrave-Graham과 Joux는^[6] $O(2^{.256n})$ O ( $O(2^{.256n})$ $O(2^{.337n})$ $){\displaystyle O (2$ $){.$ $337n}$ 을(를) 사용하여 $O(2^{.337n})$ 이전의 $O(2^{.337n})$ 알고리즘보다 빠르게 실행되는 확률 알고리즘을 제시했다 $O(2^{.256n})$ 결정 문제만 해결하고, 주어진 합에 대한 해결책이 없음을 증명할 수 없으며, T에 가장 가까운 부분집합은 반환하지 않는다.

이후 Howgrave-Graham과 Joux의 기법이 확장되어 시간 $O(2^{.291n})$ 이 $O(2^{.291n})$ O ( $O(2^{.291n})$ . $O(2^{.291n})$ n ) $O(2^{.291n})$ {\ $displaystyle O$ ( $2^{.291n})}$ 에 이르렀다 $O(2^{.291n})$

의사-폴리놈 시간 동적 프로그래밍 솔루션

SSP는 동적 프로그래밍을 사용하여 의사-폴리놈 시간 내에 해결할 수 있다. 예를 들어 다음과 같은 요소 시퀀스가 있다고 가정해 보십시오.

x_{1},\ldots,x_{N}

우리는 상태를 한 쌍의 정수로 정의한다. 이 상태는 라는 사실을 나타낸다.

"

x_{1},\ldots ,x_{i}

,

x_{1},\ldots ,x_{i}

x_{1},\ldots ,x_{i}

i

{\

의 비어 있지 않은 부분 집합이 있으며, 이 부분

x_{1},\ldots ,x_{i}

집합은

s

에 해당된다."

각 주(i, s)에는 다음 두 개의 주가 있다.

(i+1, s) $x_{i+1}$ $x_{i+1}$ + 1 ${\$ }이 $($ 가) 하위 집합에 포함되지 $x_{i+1}$ 않음을 암시하는,
( $x_{i+1}$ +1, s+ x $x_{i+1}$ + $x_{i+1}$ ${\$ x i + $x_{i+1}$ ${\$ 가 하위 집합에 포함됨을 $x_{i+1}$ 의미한다. $x_{i+1}$

초기 상태(0, 0)부터 임의의 그래프 검색 알고리즘(예: BFS)을 사용하여 상태(N, T)를 검색할 수 있다. 만약 상태가 발견되면, 역추적을 통해 우리는 정확히 T의 합을 가진 하위 집합을 찾을 수 있다.

이 알고리즘의 런타임은 상태 수에서 최대 선형이다. 주의 수는 최대 N배이다. 가능한 다른 합계의 수입니다. Let $A$ be the sum of the negative values and $B$ the sum of the positive values; the number of different possible sums is at most B-A, so the total runtime is in $O(N(B-A))$ . For example, if all input values are positive and bounded by some constant C, then B is at most N C, so the time required is $O(N^{2}C)$ $O(N^{2}C)$ $O(N^{2}C)$ ) $O(N^{2}C)$ .

$B-A$ - $B-A$ $B-A$ 은(는) 문제의 크기에서 다항식이 아니기 $B-A$ 때문에 이 솔루션은 복잡성 이론에서 다항식 시간으로 계산되지 않으며, 이는 문제를 나타내는 데 사용되는 비트의 수입니다. 이 알고리즘은 $A$ 와 $B$ 의 값에서 다항식이며, A와 B의 비트 수가 기하급수적이다. 단, 단수로 인코딩된 Subset Sum은 P로 되어 있고, 그 이후 인코딩의 크기는 B-A로 선형이다. 따라서 서브셋 합계는 약하게 NP-완전일 뿐이다.

각 $x_{i}$ $x_{i}$ ${\$ 가 $x_{i}$ 양이고 고정 상수 $C$ 에 의해 경계되는 경우에 대해, 피싱거는 시간 복잡성이 $O(NC)$ ( $O(NC)$ C $O(NC)$ ) ${\displaystyle$ O $(NC)}$ 인 선형 시간 알고리즘을 발견했다( $O(NC)$ 이는 목표 합이 반드시 0이 아닌 문제의 버전을 위한 것이라는 점에 유의한다).^[8] 2015년 Koapariis와 Shu는 우리가 $찾아야$ 할 총액인 부분집합 문제에 대한 결정론적 ${\tilde {O}}(T{\sqrt {N}})$ ~ ${\tilde {O}}(T{\sqrt {N}})$ (T ${\tilde {O}}(T{\sqrt {N}})$ ) ${\displaystyle {\tilde{O}(T{\sqrt{N})$ 알고리즘을 ${\tilde {O}}(T{\sqrt {N}})$ 발견했다.^[9] 2017년, Bringmann은 랜덤화된 ${\tilde {O}}(T+N)$ ~ ${\tilde {O}}(T+N)$ + ${\tilde {O}}(T+N)$ $){\displaystyle {\tilde{O}}(T+N)}$ 시간 ${\tilde {O}}(T+N)$ 알고리즘을 발견했다.^[10]

In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having $O(N(m-x_{\min })/p)$ time and $O(N+m-x_{\min })$ space, where $p$ is the number of processing elements, ${\displaystyle m=\$ $min(s,\sum x_{i}-s)$ 및 $m=\min(s,\sum x_{i}-s)$ $x_{\min }$ ${\$ 은(는) 가장 낮은 정수다 $x_{\min }$ .^[11] 이것은 지금까지 알려진 것 중 최고의 이론적 병렬 복잡성이다.

SSP의 실제 결과와 하드 인스턴스 해결책의 비교는 Curtis와 Sanches에 의해 논의된다.^[12]

다항 시간 근사 알고리즘

모든 입력이 양수라고 가정합시다. SSP에 대한 근사 알고리즘은 최대 T의 합과 최소 r배의 최적 합을 가진 S의 부분 집합을 찾는 것을 목표로 한다. 여기서 r은 근사비라고 불리는 (0,1)의 숫자다.

단순 1/2 근사치

다음의 매우 간단한 알고리즘은 근사비가 1/2이다.^[13]

입력 값을 내림차순으로 정렬한다.
다음으로 큰 입력은 거기에 맞는 한 하위 집합에 넣으세요.

이 알고리즘이 종료되면 모든 입력이 하위 집합(분명히 최적임)에 있거나 맞지 않는 입력이 있다. 첫 번째 그러한 입력은 하위 집합에 있는 이전의 모든 입력보다 작으므로 T/2보다 작아야 한다. 따라서 하위 집합의 입력 합계가 T/2보다 많으며, 이는 분명히 OPT/2보다 많다.

완전 다항식 시간 근사 방식

다음 알고리즘은 $\epsilon >0$ > $\epsilon >0$ $\epsilon >0$ 마다 $\epsilon >0$ $(1-\epsilon )$ - $(1-\epsilon )$ ) {\ $displaystyle (1-\epsilon )}$ 의 근사 비율을 얻는다 $(1-\epsilon )$ 실행 시간은 $n$ 과 1 / $1/\epsilon$ ${\displaystyle 1/\epsilon$ $1/\epsilon$ n은 입력의 수이고 T는 부분집합에 대한 상한이다.

각 나는 1n까지 우일 목록을 모든 요소 L에 y을 포함한 것 같아요, 그리고 모든 총액+y는 L. 종류 우이의 모든 y에 대해 우이의 나는 빈 빛 y 가장 작은 요소를 상행에서 L에 우이의 각 요소 z가 증가하고 있어 주문 y을 추가하 xi을 무감각해 짐을 없앰으로써 목록// 하는 목록 나는 기분이 하나의 요소 0을 포함하도록 초기화합니다.cers서로 //에 지고 목표 합계 T보다 큰 원소를 버린다. y + + T/n < z ≤ T인 경우 y = z add z는 L에 가장 큰 원소를 반환한다.

트리밍 단계(각 루프에 대한 내부 "")가 없으면 목록 L에는 입력의 $2^{n}$ ${\$ 2 $^{n}$ 하위 집합의 $2^{n}$ 합계가 모두 포함된다. 트리밍 스텝은 두 가지 일을 한다.

그것은 L에 남아 있는 모든 합이 T 이하임을 보장하므로 부분집합 문제에 대한 실현 가능한 해결책이다.
리스트 L이 "sparse" 즉, 각 연속 부분섬의 차이가 최소한 $\epsilon T/n$ $\epsilon T/n$ / $\epsilon T/n$ $\epsilon T/n$ 임을 보장한다 $\epsilon T/n$

이러한 속성은 목록 $n/\epsilon$ 에 n / $n/\epsilon$ ${\displaystyle$ n $/\epsilon }$ 개 $n/\epsilon$ 이상의 요소가 포함되어 있지 않음을 보장하므로 $n/\epsilon$ 은 n / $n/\epsilon$ {\ $displaystyle$ n $/\epsilon$ $n/\epsilon$ 의 다항식이 된다.

알고리즘이 종료되면 최적 $합계$ 가 L이면 반환되고 우리는 끝난다. 그렇지 않으면 이전 트리밍 단계에서 제거했을 것이다. 각 트리밍 단계에서는 최대 $\epsilon T/n$ $\epsilon T/n$ ${\displaystyle \epsilon T/n$ 의 추가 오차를 도입하므로, $N$ 스텝은 최대 together $\epsilon T$ $\epsilon T$ 의 오류를 도입한다 $\epsilon T$ 따라서 반환되는 솔루션은 적어도 ${\text{OPT}}-\epsilon T$ - ${\text{OPT}}-\epsilon T$ - ${\text{OPT}}-\epsilon T$ ${\displaystylease {\ty$ }이다 $.$ $OPT}-\epsilon T}($ 최소 ${\text{OPT}}-\epsilon T$ $(1-\epsilon ){\text{OPT}}$ ( $(1-\epsilon ){\text{OPT}}$ - $(1-\epsilon ){\text{OPT}}$ ) $(1-\epsilon ){\text{OPT}}$ ${\$ $OPT}}$ $(1-\epsilon ){\text{OPT}}$ .

위의 알고리즘은 입력 숫자가 작을 경우(그리고 음수가 아닐 경우) SSP에 정확한 솔루션을 제공한다. 만약 숫자의 합이 최대 $P$ 비트로 지정될 수 있다면, 대략 $\epsilon =2^{-P}$ = 2 $\epsilon =2^{-P}$ - $\epsilon =2^{-P}$ ${\$ 로 문제를 해결하는 것은 정확히 해결하는 것과 같다 $\epsilon =2^{-P}$ . 그런 다음, 대략적인 부분집합에 대한 다항식 시간 알고리즘은 running time 다항식을 $n$ 및 2 $2^{P}$ ${\$ 즉, $지수$ P)로 하는 정확한 알고리즘이 된다.

Kelerer, Mansini, Piperschy^[14] 및 Speranza와 Kelerer, Piperschy 및 Pisinger는^[15] 부분집합에 대한 다른 FPTAS-s를 제시한다.

다항 시간 알고리즘

^[16] 이것은 서브셋을 찾는 데 사용할 수 있는 다항식 시간 알고리즘이다.

참고 항목

배낭 문제 - 각 입력 항목이 값과 가중치를 모두 갖는 SSP의 일반화. 총중량이 경계되도록 값을 최대화하는 것이 목표다.
다중 부분 집합 합계 문제 - 여러 하위 집합을 선택해야 하는 SSP의 일반화.
3SUM
머클-헬만 배낭 암호체계
높은 확률로 저밀도 SSP를 해결하기 위한 알고리즘.^[17]
4 부분집합 문제.^[18]

참조

^ ^a ^b Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design (2nd ed.). p. 491. ISBN 0-321-37291-3.
^ Goodrich, Michael. "More NP complete and NP hard problems" (PDF).
^ ^a ^b ^c Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt (2014). "Optimal Sequential Multi-Way Number Partitioning" (PDF).{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
^ Horowitz, Ellis; Sahni, Sartaj (1974). "Computing partitions with applications to the knapsack problem" (PDF). Journal of the Association for Computing Machinery. 21 (2): 277–292. doi:10.1145/321812.321823. hdl:1813/5989. MR 0354006. S2CID 16866858.
^ Schroeppel, Richard; Shamir, Adi (1981-08-01). "A $T = O (2 n /2)$ , $S = O (2 n /4)$ algorithm for certain NP-complete problems". SIAM Journal on Computing. 10 (3): 456–464. doi:10.1137/0210033. ISSN 0097-5397.
^ Howgrave-Graham, Nick; Joux, Antoine (2010). Gilbert, Henri (ed.). "New Generic Algorithms for Hard Knapsacks". Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6110: 235–256. doi:10.1007/978-3-642-13190-5_12. ISBN 978-3-642-13190-5.
^ Becker, Anja; Joux, Antoine (2010). Gilbert, Henri (ed.). "Improved Generic Algorithms for Hard Knapsacks". Advances in Cryptology – EUROCRYPT 2011. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6632: 364–385. doi:10.1007/978-3-642-20465-4_21. ISBN 978-3-642-20465-4.
^ Pisinger, David (1999). "Linear time algorithms for knapsack problems with bounded weights". Journal of Algorithms. 33 (1): 1–14. doi:10.1006/jagm.1999.1034. MR 1712690.
^ Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "A Faster Pseudopolynomial Time Algorithm for Subset Sum". arXiv:1507.02318 [cs.DS].
^ Bringmann, Karl (2017). "A near-linear pseudopolynomial time algorithm for subset sum". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). SIAM. pp. 1073–1084. arXiv:1610.04712. doi:10.1137/1.9781611974782.69.
^ Curtis, V. V.; Sanches, C. A. A. (January 2016). "An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU". Concurrency and Computation: Practice and Experience. 28 (1): 95–113. doi:10.1002/cpe.3636. S2CID 20927927.
^ Curtis, V. V.; Sanches, C. A. A. (July 2017). "A low-space algorithm for the subset-sum problem on GPU". Computers & Operations Research. 83: 120–124. doi:10.1016/j.cor.2017.02.006.
^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "The Multiple Subset Sum Problem". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.
^ Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "An efficient fully polynomial approximation scheme for the Subset-Sum Problem". Journal of Computer and System Sciences. 66 (2): 349–370. doi:10.1016/S0022-0000(03)00006-0. ISSN 0022-0000.
^ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Knapsack problems. Springer. p. 97. ISBN 9783540402862.
^ Kulkarni, Sanket (2022-01-24). Polynomial time algorithm for subset sum problem. doi:10.13140/rg.2.2.14508.95365.
^ Lagarias, J. C.; Odlyzko, A. M. (1985-01-01). "Solving low-density subset sum problems". Journal of the ACM. 32 (1): 229–246. doi:10.1145/2455.2461. ISSN 0004-5411.
^ Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.

추가 읽기

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "35.5: The subset-sum problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, 페이지 223.

[kleinberg2006p491-1] Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design (2nd ed.). p. 491. ISBN 0-321-37291-3.

[2] Goodrich, Michael. "More NP complete and NP hard problems" (PDF).

[:0-3] Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt (2014). "Optimal Sequential Multi-Way Number Partitioning" (PDF).{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)

[4] Horowitz, Ellis; Sahni, Sartaj (1974). "Computing partitions with applications to the knapsack problem" (PDF). Journal of the Association for Computing Machinery. 21 (2): 277–292. doi:10.1145/321812.321823. hdl:1813/5989. MR 0354006. S2CID 16866858.

[5] Schroeppel, Richard; Shamir, Adi (1981-08-01). "A $T = O (2 n /2)$ , $S = O (2 n /4)$ algorithm for certain NP-complete problems". SIAM Journal on Computing. 10 (3): 456–464. doi:10.1137/0210033. ISSN 0097-5397.

[6] Howgrave-Graham, Nick; Joux, Antoine (2010). Gilbert, Henri (ed.). "New Generic Algorithms for Hard Knapsacks". Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6110: 235–256. doi:10.1007/978-3-642-13190-5_12. ISBN 978-3-642-13190-5.

[7] Becker, Anja; Joux, Antoine (2010). Gilbert, Henri (ed.). "Improved Generic Algorithms for Hard Knapsacks". Advances in Cryptology – EUROCRYPT 2011. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6632: 364–385. doi:10.1007/978-3-642-20465-4_21. ISBN 978-3-642-20465-4.

[Pisinger09-8] Pisinger, David (1999). "Linear time algorithms for knapsack problems with bounded weights". Journal of Algorithms. 33 (1): 1–14. doi:10.1006/jagm.1999.1034. MR 1712690.

[9] Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "A Faster Pseudopolynomial Time Algorithm for Subset Sum". arXiv:1507.02318 [cs.DS].

[10] Bringmann, Karl (2017). "A near-linear pseudopolynomial time algorithm for subset sum". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). SIAM. pp. 1073–1084. arXiv:1610.04712. doi:10.1137/1.9781611974782.69.

[11] Curtis, V. V.; Sanches, C. A. A. (January 2016). "An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU". Concurrency and Computation: Practice and Experience. 28 (1): 95–113. doi:10.1002/cpe.3636. S2CID 20927927.

[12] Curtis, V. V.; Sanches, C. A. A. (July 2017). "A low-space algorithm for the subset-sum problem on GPU". Computers & Operations Research. 83: 120–124. doi:10.1016/j.cor.2017.02.006.

[:1-13] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "The Multiple Subset Sum Problem". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.

[14] Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "An efficient fully polynomial approximation scheme for the Subset-Sum Problem". Journal of Computer and System Sciences. 66 (2): 349–370. doi:10.1016/S0022-0000(03)00006-0. ISSN 0022-0000.

[knapsack-15] Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Knapsack problems. Springer. p. 97. ISBN 9783540402862.

[16] Kulkarni, Sanket (2022-01-24). Polynomial time algorithm for subset sum problem. doi:10.13140/rg.2.2.14508.95365.

[17] Lagarias, J. C.; Odlyzko, A. M. (1985-01-01). "Solving low-density subset sum problems". Journal of the ACM. 32 (1): 229–246. doi:10.1145/2455.2461. ISSN 0004-5411.

[MartelloToth-18] Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.

[1]

[2]

[3]

[4]

[6]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Search