knapsack problem은 O(n²V)
시간에 풀릴 수 있습니다. 여기서 V = max(v[i], i = 1,..,n)
은 항목의 최대 값을 나타냅니다. 반올림 매개 변수 θ = ε/n * V
으로 "단위 변경"을 수행하고 수정 된 값인 y[i] = ceil(v[i]/θ)
을 고려하면 에 대한 실행 시간은 O(n³/ε)
이며ε > 0
으로 고정됩니다. 존 클라인 버그에 의해 도서 알고리즘 디자인에서 배낭의 다항식 시간 근사
1/ε
보다는
log 1/ε
포함으로 원하는 정밀도
ε
에
의존성은 다항식 없습니다. 모든
첫째, 용어 의사 다항식 뒤에 전체 아이디어는 내가 그것에 대해 몇 가지 기사를 읽었습니다에도 불구하고, 나에게 정확하게 명확하지 않다. 그러나이 지식 격차 외에도 주로 실행 시간에 1/ε
대신 log 1/ε
이 포함될 경우 ε
에 대한 종속성이 다항식이되는 이유를 스스로 묻습니다.
'log 1/ε'은 대략 2 진수로 '1/ε'을 저장하는 데 필요한 비트 수입니다. - 나에게 절대적으로 명확하지만, 왜 문제가됩니까? 'O (n^k)'의'n '에 대해서도 같은 방식으로 논할 수는 없었습니까? 'n'이 단지 루프 카운터 일지라도, (일반적으로) 그 값을 저장해야합니다. 그래서'n '을'1/ε'과 다른 점은 무엇입니까? [또한, 왜 어떤 매개 변수의 단항 표현을 고려할 것입니까?] – 0xbadf00d
@ 0xbadf00d 'n'이 목록의 요소의 개수라면, 목록 요소 자체는 선형 비트 수를 사용하여 정렬합니다 무의미한 'n'표현 방법. 'n '이 단지 숫자 일 경우 (예를 들어, 팩토링을 위해), 그것은'1/ε '과 같은 방식으로 취급됩니다. –
@ 0xbadf00d 단항 표현에 대해 생각하는 이유는 의사 - 다항식 시간이 공식적으로 정의되는 방식이기 때문입니다. 사람들은 Stack Overflow에서 배낭 변형에 대해 자주 묻습니다. 의견이나 답변 중 하나는 "NP가 힘들고 운이 없다"는 것입니다. 그러나 배낭은 약하게 NP 하드이기 때문에, 작은 정수 입력에서 잘 작동하는 알고리즘이 존재하며, 이는 실제로 매우 유용합니다. 반면에 [3-partition] (http://en.wikipedia.org/wiki/3-partition_problem)은 작은 정수 입력이 더 쉽지 않습니다. –