[algorithm] 배낭 문제를 이해하는 방법은 NP 완전입니까?
배낭 문제는 동적 프로그래밍을 통해 O (nW) 복잡성으로 해결할 수 있다는 것을 알고 있습니다. 그러나 우리는 이것이 NP 완전 문제라고 말합니다. 여기서 이해하기 어렵다고 생각합니다.
(n은 항목 수입니다. W는 최대 볼륨입니다.)
답변
O(n*W)외모는 다항식 시간을 좋아하지만은 없습니다 그것은이다, 의사 다항식 .
시간 복잡도는 알고리즘이 입력 비트 의 길이 함수로 걸리는 시간을 측정합니다 . 동적 프로그래밍 솔루션은 실제로 의 값에서 선형 적이W 지만 길이W 에서는 기하 급수적이며 그게 중요한 것입니다!
더 정확하게는 배낭 문제에 대한 동적 솔루션의 시간 복잡성 은 기본적으로 중첩 루프에 의해 제공됩니다.
// here goes other stuff we don't care about
for (i = 1 to n)
for (j = 0 to W)
// here goes other stuff
따라서 시간 복잡성은 명확 O(n*W)합니다.
알고리즘의 입력 크기를 선형 적으로 증가 시킨다는 것은 무엇을 의미합니까? 그것은 점진적으로 더 이상 항목의 배열 (그래서 사용하는 것을 의미 n, n+1, n+2점진적 이상, …)와 W(그래서, 경우가 W있다 x비트가 한 단계 이후에 우리가 사용하는 긴 x+1다음 비트, x+2비트, …). 그러나의 값W 은로 기하 급수적 으로 증가 x하므로 알고리즘은 실제로 다항식이 아니라 지수 적입니다 (그러나 다항식처럼 보이므로 이름 : “의사 다항식”).
추가 참조
답변
배낭 0/1 문제에서이 문제를 해결하려면 입력 2 개 (배열 1 개와 정수 1 개)가 필요합니다.
- n 개 항목 의 배열 : [n1, n2, n3, …], 각 항목에는 값 인덱스와 가중치 인덱스가 있습니다.
- 최대 허용 무게로 정수 W
n = 10 및 W = 8이라고 가정 해 보겠습니다.
- n = [n1, n2, n3, …, n10]
- W = 1000 이진 항 (4 비트 길이)
따라서 시간 복잡도 T (n) = O (nW) = O (10 * 8) = O (80)
당신은 두 번 경우 N의 크기 :
n = [n1, n2, n3, …, n10 ]-> n = [n1, n2, n3, …, n20 ]
따라서 시간 복잡도 T (n) = O (nW) = O (20 * 8) = O (160)
그러나 W의 크기 를 두 배로 늘리면 W = 16을 의미하지는 않지만 길이는 두 배 더 길어집니다.
W = 1000-> W = 10000000 (2 진수) (8 비트 길이)
그래서 T (n) = O (nW) = O (10 * 128) = O (1280)
필요한 시간이 기하 급수적으로 증가하므로 NPC 문제입니다.
답변
그것은 모두 당신이 어떤 매개 변수를 넣느냐에 달려 있습니다 O(...).
목표 무게가 숫자 W에 의해 제한되면 O(n*W)언급했듯이 문제가 복잡해집니다.
그러나 가중치가 너무 크고 복잡도에 독립적 인 알고리즘이 필요한 W경우 문제는 NP 완료입니다. ( O(2^n*n)대부분의 순진한 구현에서).
답변
이는 배낭 문제 에 의사 다항식 솔루션이있어서 약한 NP-Complete ( 강력한 NP-Complete 아님) 라고 불리기 때문 입니다.
답변
입력 크기는 log(W)가중치 (및 O(n)“값”및 “가중”배열)에 대한 비트입니다 .
따라서 가중치의 입력 크기는 j = log(W)(단순한 것이 W아님)입니다. 그래서 W = 2ʲ(바이너리가 사용됨).
마지막 복잡성은 O(n * W)
이것은 입력 크기에서 기하 급수적 인
O(n * W)로 다시 작성할 수 있습니다O(n * 2ʲ).
따라서이 솔루션은 다항식이 아닙니다.
