0-1 반복이없는 배낭

Question

내 질문은 배낭 문제의 o (nw)가 의사 - 다항식이기 때문입니다.

나는 Stackoverflow에서 많은 설명을 읽었지 만, 나는 그것을 정말로 이해하지 못한다. ( https://stackoverflow.com/question. / 19647658 / what-is-pseudopolynomial-time-hos-diffic-dimomial-time , https://stackoverflow.com/questions/4538581/why- is-the-the-the-the-the-pershial-pseudo-polynomial # answer-4538668 )

핵심 점은 'logw'비트로 'n'이 아닌 'n'을 'logn'으로 생각하는 것으로 생각 해야하는 이유입니다.

많은 설명은 'W'가 정수이지만 'n'은 항목 수입니다. 따라서 'W'크기 만 'logw'에 비례합니다.

이 논리를 'n'에 적용해야한다고 생각합니다.

아이템을 차별화하기 위해 1에서 n까지 항목을 번호를 지정하고 있다고 가정합니다.

우리는 1에서 n까지 숫자를 계산해야합니다.

나는 루프가 W 타임에 반복되는 것과 동일하다고 생각합니다.

이므로이 계수가 'log n'비트가 필요하기 때문에 'W'와 동일하다고 생각합니다.

이 문제에서 잘못 이해할 수 있습니까?

감사합니다.

Answer 1

여기에 입력을 인코딩하는 방법이 있습니다.

• 품목 1의 체중 및 가치.
• 무게와 항목 2의 가치.
• ...
• 항목 $ N $ .
• $ W $ .

가중치와 값이 정수이고, 대부분의 $ m $ 모두 $ W $ .그런 다음 인코딩의 길이는입니다 $$ \ 오메가 (n + \ log w), o (n \ log m + \ log w). $$ 바라건대 이것은 $ n $ 및 $ W $ 의 차이를 명확히합니다.