배낭 문제를 이해하는 방법은 NP 완전입니까?

배낭 문제를 이해하는 방법은 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하므로 알고리즘은 실제로 다항식이 아니라 지수 적입니다 (그러나 다항식처럼 보이므로 이름 : "의사 다항식").

---

추가 참조

• http://www.cs.ship.edu/~tbriggs/dynamic/index.html
• http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

---

배낭 0/1 문제에서이 문제를 해결하려면 입력 2 개 (배열 1 개와 정수 1 개)가 필요합니다.

1. n 개 항목 의 배열 : [n1, n2, n3, ...], 각 항목에는 값 인덱스와 가중치 인덱스가 있습니다.
2. 최대 허용 무게로 정수 W

---

n = 10 및 W = 8이라고 가정합니다.

1. n = [n1, n2, n3, ..., n10]
2. 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)언급했듯이 문제가 복잡해집니다.

그러나 가중치가 너무 크고 복잡한 알고리즘이 필요하면 WNP- 완전한 문제입니다. ( 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ʲ).

따라서이 솔루션은 다항식이 아닙니다.

---

이 짧은 설명을 읽을 수 있습니다. The NP-Completeness of Knapsack .

---

NP- 완전성 을 이해하려면 약간의 복잡성 이론을 배워야합니다. 그러나 기본적으로 배낭 문제에 대한 효율적인 알고리즘은 SAT , TSP 및 나머지에 대한 효율적인 알고리즘이기 때문에 기본적으로 NP 완료 입니다.

참고 URL : https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete